소수 개수 구하기(에라토스테네스의 체)

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)

 

1부터 n까지의 소수 개수를 구할 땐 에라토스테네스의 체 알고리즘을 이용하자

 

1. ch리스트를 만들어 배열을 0으로 초기화한다. (cn[i]==0 이면 소수를 의미)

2. i가 2부터 n까지 반복하면서

3. ch[i]==0이면 소수이므로 cnt 증가시키고

4. i의 배수를 모두 1로 표시하여 소수가 아님을 체크한다.

5. 최종적으로 cnt에 소수 개수가 저장되어 출력한다.

 

True, False로 변형 가능

1. ch리스트를 만들어 True로 초기화(True는 소수를 의미)

2. i가 2부터 n까지 반복하면서

3. ch[i]==True이면 소수로 판단, cnt를 증가시키고 해당  i값을 출력한다.

4. i의 배수를 False로 바꿔서 소수가 아님을 표시한다.

5. 최종적으로 cnt에 소수 개수가 저장되어 출력한다.

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