첫 시도
def checkPrime(n):
hit = 0
for x in range(2, int(n**0.5) + 1):
if n % x == 0 :
hit += 1
break
if(hit != 0):
return False
else: return True
def solution(n):
answer = 0
for x in range(2,n+1):
if checkPrime(x):
answer += 1
return answercheckPrime()
첫 시도에는 원래 range(2, n)을 썼더니 테스트가 끝나지 않아서 찾아보니..
루트를 씌워서 +1을 해도 된다는 것을 발견했다.
어차피 소수가 아니라면 루트값을 기준으로 약수들이 대칭이 되기 때문.
range 값으로 float를 넘길 수 없으니 int(n**0.5)를 해주고 여기까지 포함될 수 있도록 +1을 해준다.
2부터 나누어 지는지 체크해서 0으로 나누어 떨어지는 즉시 hit값을 올려서 룹을 빠져 나오게 된다. 소수라면 hit을 바꾸지 않아서 True 리턴, 아니라면 False.
solution()
answer 이라는 인트타입 지역변수를 만들어서 2부터 n까지 for-loop을 돌려 checkPrime()이 True리턴을 하면 하나씩 더하는 걸로 설정하였다.
그런데 성능이 너무 나쁨..🥲
다른 사람의 풀이
다른 풀이를 보니 set()을 이용하여 n까지의 수를 넣어주고 그 수와 그 수의 배수를 set()에서 제외 시키는 방식을 사용하였다. 이게 에라토스테네스의 체인가보다..
다만 맨처음 set()의 범위를 어떻게 적용해주었는지에 따라 성능 차이가 발생하였다
range(2,n+1)
def solution(n):
num =set(range(2,n+1))
for i in range(2,n+1):
if i in num:
num-=set(range(2*i,n+1,i))
return len(num)range(3,n+1,2)
def solution(n):
num = set(range(3,n+1,2))
for i in range(3,n+1,2):
if i in num:
num -= set(range(i*2,n+1,i))
return len(num)+1맨 처음 set() 을 설정할 때
range(2,n+1) : 2, 3, 4, 5, 6, 7, 8, 9, 10
range(3,n+1,2) : 3, 5, 7, 9
range(3,n+1,2)는 3에서부터 2씩 증가하게하여 아예 짝수를 배제시켜 버림으로써 성능향상이 이루어 졌다. 다만 주의하여야 할 것은 이렇게 짝수를 배제시켜 버릴 때 시작 숫자가 1이나 3같은 홀수여야 한다는 것.
3으로 시작하면 매 계산마다 1은 제외 시킬 수 있으므로 약간의 이득이 있다.
다만 마지막 리턴할 때 +1을 해서 1을 포함시켜 줄수 있도록 한다
if i in num: 조건으로 이미 제외된 수를 재조사?하는 것을 방지할 수 있다
아래는 n = 30일 때 진행 과정이다.
1. 3의 배수제외
2. 5의 배수제외
3. 7의 배수제외
등 순차적으로 소수의 배수를 제외해 나가는 것을 확인할 수 있다.
{3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29} - {6, 9, 12, 15, 18, 21, 24, 27, 30}
{3, 5, 7, 11, 13, 17, 19, 23, 25, 29} - {10, 15, 20, 25, 30}
{3, 5, 7, 11, 13, 17, 19, 23, 29} - {28, 21, 14}
{3, 5, 7, 11, 13, 17, 19, 23, 29} - {22}
{3, 5, 7, 11, 13, 17, 19, 23, 29} - {26}
{3, 5, 7, 11, 13, 17, 19, 23, 29} - set()
{3, 5, 7, 11, 13, 17, 19, 23, 29} - set()
{3, 5, 7, 11, 13, 17, 19, 23, 29} - set()
{3, 5, 7, 11, 13, 17, 19, 23, 29} - set()성능 비교
| 첫 시도 | range(2,n+1) | range(3,n+1,2) | |
|---|---|---|---|
| 테스트 1 〉 | 통과 (0.01ms, 10.1MB) | 통과 (0.00ms, 10.3MB) | 통과 (0.00ms, 10.2MB) |
| 테스트 2 〉 | 통과 (0.10ms, 10.2MB) | 통과 (0.07ms, 10MB) | 통과 (0.03ms, 10.1MB) |
| 테스트 3 〉 | 통과 (0.27ms, 10.4MB) | 통과 (0.29ms, 10.2MB) | 통과 (0.08ms, 10.1MB) |
| 테스트 4 〉 | 통과 (0.58ms, 10.1MB) | 통과 (0.39ms, 10.1MB) | 통과 (0.31ms, 10.1MB) |
| 테스트 5 〉 | 통과 (0.38ms, 10.1MB) | 통과 (0.17ms, 10.3MB) | 통과 (0.19ms, 10.2MB) |
| 테스트 6 〉 | 통과 (6.77ms, 10.1MB) | 통과 (2.50ms, 11.1MB) | 통과 (1.66ms, 10.4MB) |
| 테스트 7 〉 | 통과 (1.62ms, 10.2MB) | 통과 (1.16ms, 10.3MB) | 통과 (0.44ms, 10.2MB) |
| 테스트 8 〉 | 통과 (4.53ms, 10.1MB) | 통과 (1.88ms, 10.9MB) | 통과 (1.20ms, 10.5MB) |
| 테스트 9 〉 | 통과 (9.35ms, 10.2MB) | 통과 (4.28ms, 11MB) | 통과 (2.08ms, 10.6MB) |
| 테스트 10 〉 | 통과 (586.34ms, 10MB) | 통과 (81.22ms, 45.5MB) | 통과 (63.25ms, 27.9MB) |
| 테스트 11 〉 | 통과 (2937.63ms, 10.2MB) | 통과 (347.95ms, 113MB) | 통과 (217.76ms, 63.3MB) |
| 테스트 12 〉 | 통과 (724.48ms, 10MB) | 통과 (100.91ms, 47MB) | 통과 (76.56ms, 28.5MB) |
| 테스트 1 〉 | 통과 (3251.28ms, 9.96MB) | 통과 (347.99ms, 116MB) | 통과 (204.96ms, 64.9MB) |
| 테스트 2 〉 | 통과 (2922.52ms, 9.97MB) | 통과 (339.79ms, 115MB) | 통과 (333.49ms, 64.1MB) |
| 테스트 3 〉 | 통과 (4675.81ms, 10.1MB) | 통과 (346.02ms, 116MB) | 통과 (221.11ms, 64.6MB) |
| 테스트 4 〉 | 통과 (3127.34ms, 10.1MB) | 통과 (340.76ms, 115MB) | 통과 (213.15ms, 64.5MB) |
