728x90
반응형
SMALL
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
| n | result |
| 10 | 4 |
| 5 | 3 |
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
--------------------------------------------------------------------------------------------------------------------
문제 풀이
1) 소수 찾기 기본 코드
조건식을 이용하여 나누어 떨어짐을 확인한다. 검사 끝은 i 에 루트(i**0.5, )를 적용한 수 까지 찾는다.
def solution(n):
answer = 0
for i in range(2,n+1):
prime = True
for j in range(2,int(i**0.5)+1):
if i%j==0:
prime = False
break
if prime:
answer += 1
return answer효율성 결과는?
2) 효율성 개선 코드
체크 해야될 수 중에서 짝수와 짝수 약수를 제거하여 아래와 같이 코드를 변경하였다.
def solution(n):
answer = 1
for i in range(3,n+1,2):
prime = True
for j in range(3,int(i**0.5)+1,2):
if i%j==0:
prime = False
break
if prime:
answer += 1
return answer효율성 결과는? 약 2배정도 빠라짐을 확인할 수 있다.
728x90
반응형
LIST
'IT > 코딩테스트' 카테고리의 다른 글
| 프로그래머스 실패율 문제 풀이 시간단축 최적화 코드 (0) | 2024.05.16 |
|---|---|
| 프로그래머스 소수 만들기 문제 설명 풀이 코드 (1) | 2024.05.15 |
| 프로그래머스 과일 장수 설명, 코딩, 답 (0) | 2024.05.14 |
| 프로그래머스 모의고사 문제 답 코딩 (1) | 2024.05.14 |
| 프로그래머스 폰켓몬 설명 풀이 코드 답 코딩 (0) | 2024.05.14 |
