programmers.co.kr/learn/courses/30/lessons/12921
코딩테스트 연습 - 소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상
programmers.co.kr
처음 시도한 방식은 시간초과가 걸렸다.
3 이상의 홀수에 대해서만 소수검사를 실시하고
소수검사에서는 숫자 n을 3~ n//2+1에 해당하는 홀수로 나눠보면서 프라임넘버 여부를 확인했다.
예를 들어 n = 37이면 (3~19)에 속하는 홀수인 3,5,7,9,11,13,15,17,19을 차례대로 나눠보는 것이다.
문제에서 n의 범위가 100만이다보니 이렇게 O(n2)로 짜면 n이 큰 수 일때 어마어마한 시간이 소요된다.
def solution(n):
def isPrime(n):
for i in range(3,(n//2)+1,2):
if n%i ==0:
return False
return True
count =1
for i in range(3,n+1,2):
if isPrime(i):
count +=1
return count근데 생각해보니 3으로 나눠 떨어지지 않았다면 후에 3의 배수인 9,15 같은 수로는 나눠볼 필요가 없었다.
이 부분을 캐치하고 개선해보았다.
프라임넘버를 찾으면 리스트에 담아두면서 나중에 검사할 때 이 프라임넘버로만 나눠보는 방식으로 짰다.
시간이 많이 개선되었으나 여전히 타임아웃이 발생했다.
def solution(n):
pm = []
def isPrime(n):
for p in pm:
if n%p ==0:
return False
pm.append(n)
return True
count =1
for i in range(3,n+1,2):
if isPrime(i):
count +=1
return count
그러다가 프라임넘버를 구하는 새로운 방법을 발견하였다.
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간
ko.wikipedia.org
참고한 코드는 다음과 같다. 성능도 매우 좋았다.
def solution(n):
sieve = [True] * (n+1)
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True:
for j in range(i+i, n+1, i):
sieve[j] = False
return sieve.count(True)-2
# prime number list
# pm = [i for i in range(2, n+1) if sieve[i] == True]
댓글