[알고리즘]소수(에라토스테네스 체)

문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.

입력예제1

20

출력예제1

8

[내 코드]

import math
def is_prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:
            return False
    return True

N=int(input())
a=[]
for i in range(2,N+1):
    if is_prime(i)==True:
        a.append(i)

print(len(a))

참고 : https://velog.io/@tkv00/알고리즘소수판별

[해설 코드]

n=int(input())
ch=[0]*(n+1)
cnt=0
for i in range(2, n+1):
	if ch[i]==0:
    	cnt+=1
        for j in range(i,n+1,i):
        	ch[j]=1
print(cnt)

이중 for문을 활용한 소수찾기 알고리즘