프로그래머스 소수찾기 PYTHON

def solution(n):
    answer = 0
    count = 0
    for i in range(2,n+1):
        for j in range(1,n+1):
            if i%j == 0:
                count += 1
        if count == 2:
            answer += 1
        print(answer)
        count = 0
    return answer

 처음 문제를 풀떄는 이중for문을 사용하여 소수를 하나씩 찾아가면 된다고 생각했다. 하지만 이런식으로 코드를 작성하니 시간초과가 나오게 되었다. 이코드의 시간복잡도는O(n2)이 된다. 그래서 시간초과가 된것이라고 생각된다.

import math
def solution(n):
    answer = [True for i in range(n+1)]
    answer[1] = False
    for i in range(2,int(math.sqrt(n)+1)):
        j = 2
        if answer[i] == True:
            while i*j <=n:
                answer[i*j] = False
                j+=1
    return answer.count(True)-1

 

 

소수를 찾는 알고리즘을 찾다보니 에라토스테네스의 체 라는 알고리즘이 있었다. 1~100까지의 수중에 소수를 찾는것을 생각해본다면,2,3,5,7,11,13,... 이런식으로 소수를 찾을수있을것이다.하지만 에라토스테네스의 체를 사용하면 100의 약수를 전부 구한다.

1,2,4,5,10,20,25,50,100가 될것이다. 그럼 100의 제곱근은 10이다. 20,25,50,100은 모두 10의 제곱근과,10보다 작거나 같은수로 표현이 가능하다. 따라서 n의 제곱근까지만 판단하면된다. 그리고 while문을 통해 i=2~10까지, 그럼 j값은2~10까지하면 (2,2),(2,3),(2,4),(2,5).... i*j가 n까지, (3,2)...,(4,2),.....이런식으로 합성수들을 전부 찾을수있다.

그럼 에라토스테네스의 체의 시간 복잡도는 O(n√n)가 된다.