파이썬 알고리즘 007 | 소수(에라토스테네스 체) ** 주기적 복습 needed

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())
res=0

for i in range(1,n+1) :
    cnt=0
    for x in range(2,i) :
        if i%x==0 :
            cnt+=1
    if cnt==0 :
        res+=1
print(res-1)

<풀이>

소수를 구할때 에라테네스체 방법을 이용하는 것이 가장 빠름

에라스토테네스란 ?
소수 갯수 구할때 리스트 정해놓고
2부터 볼때 약수갯수가 0인거 (2,3,5..)카운트하고
그의 배수들은 다 지워버리기(2의배수, 3의배수, 5의배수..)(마치 체에 거르듯이)

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)

2,3,5..같은 애들 세는 동시에 얘네의 배수칸에는 1을 넣어줌으로써
나중에 a[i]==0인 애들만 세면 그게 소수를 새는 것

<반성점>

<배운 점>

• 소수는 1보다 큰 수

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

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

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

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

• if ch[i]==0:
  cnt+=1
  for j in range(i,n+1, i) :
  ch[j]=1