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

it 취업을 위한 알고리즘 문제 풀이

문제

코드

importsys

sys.stdin = open("input.txt","rt")

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부터 N 까지 2의 배수, 3의 배수를 모두 지운다. 그리고 남는 수는 소수이다. 어떤수가 소수라면 그 어떤수의 배수는 모두 소수가 아니다. 왜나하면 어떤수를 약수로 가지기 때문이다.

* 에라토스테네스의 체는 2부터 N까지의 수를 적고 2를 제외한 2의 배수를 지우고, 3을 제외한 3의 배수를 지우고, 4는 2의 배수로 지워졌으므로 넘어가고 5를 제외한 5의 배수를 지우고 6은 2의 배수로 지워졌으므로 넘어가고, 7을 제외한 7의 배수를 지우고 ... 위 과정을 반복해서 N까지 반복하여 남는 수는 소수가 된다.

* 이를 구현하기 위해서는 길이가 N인 배열을 가지고 체크를 해주면된다.

* 인덱스 번호를 현재 소수인지 아닌지를 체크하는 수로 생각하고 해당 인덱스의 요소의 값이 0이라면 아직 배수체크가 되지 않았으므로 카운트를 증가시키고 그 인덱스의 배수는 모두 1로 체크해주고 다음 수를 확인해 나간다.