파이썬 알고리즘-7 소수(에라토스테네스 체)

7.소수(에라토스테네스 체)

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

▣ 입력설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

▣ 출력설명
첫 줄에 소수의 개수를 출력합니다.

▣ 입력예제 1
20

▣ 출력예제 1
8

내 코드

손도 못 댔다. 분명 다른데서도 풀어봤을텐데 아무 생각도 안남.

풀이

n=int(input())
cnt=0
ch=[0]*(n+1)

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)

반성점

• 이정도면 내 뇌에 문제가 있는게 아닌가 싶다.
• 소수들의 배수를 지워나간다는 논리까지는 접근했는데 구현하지 못함.

배운 것

• 한 숫자의 배수에 전부 접근하고자 할 때에는 range(start, end, start)로 하면 start의 배수만 선택해서 접근이 가능.

• 에라토스테네스의 체:

  우선 소수는 다들 알다시피 1과 자기자신으로만 나눠질 수 있는 수이다.
  그렇기 때문에 1에서 100까지 숫자 중 소수를 구한다고 할 때, (나처럼) 무식하게 구하려고 한다면 각각의 숫자 n이 2~n-1로 나눠지는지 구하면 될 것이다. 시간은 엄청 걸리겠지만..

  여기서 에라토스테네스의 체를 사용하면 훨씬 빠르게 소수를 구할 수 있는데, 소수 자신을 제외한 소수의 배수들 (3이 소수라면 그 배수인 3, 6, 9...) 은 3을 약수로 갖고 있는 숫자들이므로 당연히 3으로 나누어진다(=소수가 아니다) 라는 사실을 이용하는 방법이다.

  결국 실질적인 구현 방법은 2부터 구하려는 숫자만큼의 리스트를 0으로 초기화 하고 반복문을 만들어서, 리스트의 값이 0인 숫자(=소수)가 있다면 count를 1씩 더해준다. 그리고 그 안에서 또다른 반복문을 만들어 소수인 숫자들의 배수들만 리스트의 값을 1로 만들어준다.

  이렇게 하면 바깥쪽 반복문이 다음 숫자로 갔을 때 if문에서 리스트의 값이 0이 아닌 경우는 count도 올라가지 않고, 안의 반복문도 실행되지 않기 때문에 매우 빠르게 소수의 개수를 구할 수 있다.

  제발 나중에도 기억하고 있었으면 좋겠다.머ㅣㄹㄴ더;ㅐㅁ냫퍼 내ㅕ호ㅜㅐ로둦ㅐㅑㅇㅈ댜로ㅓ메ㅑㅈㄴ