코드도 그리 길지 않고 충분히 샘플도 통과하는데 문제를 잘 모르겠습니다

1
2
3
4
5
6
7
8
9
10
def solution(n):
    answer = 0
    for i in range(1,n+1):
        dc=0
        for a in range(1,i+1):
            if (i%a==0):
                dc+=1
        if dc==2:
            answer+=1
    return answer

• 

  에라토스네스의 소수판별에 의하면 1부터 문제에서의 n의 제곱근 까지의 수로 n을 나눴을 때 나눠지지않으면 소수입니다. 따라서 계산을 모든 수 까지 할 필요없이 1~(n의 제곱근) 까지 계산을 해주면 됩니다. 참고로 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 n의 제곱근 이하가 됩니다.

  조성진―2019.10.30 23:19