자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다.
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
첫 줄에 소수의 개수를 출력합니다.
에라토스테네스가 만들어낸 소수 판별법이다.
주어진 자연수까지 배열을 만들고 배수를 제거해 나가면 남은 숫자들이 소수가 되는 방식
자연수가 20일 경우에 순서이다.
길이 20까지의 배열을 생성한다. 1은 소수가 아니므로 제거한다.
2가 발견되고 2의 배수를 모두 지운다.
3이 발견되고 3의 배수를 모두 지운다.
[2, 3, 5, 7, 11, 13, 17, 19]
과정을 반복하고 나면 남은 수들이 소수이다.
이 개념을 바탕으로 코드를 작성해보았다.
def solution(N):
tmp = [True for _ in range(N+1)] #주어진 정수만큼 배열을 만든다
for i in range(2, N): # 1은 소수이므로 제외하고 나머지 수까지 반복한다
if tmp[i]: # 처음 발견됨=소수
print(i,end=" ")
for j in range(i+i, N+1, i): # 발견된 소수의 배수를 찾아낸다
tmp[j]=False
위의 함수에 100을 입력하면 아래와 같이 소수만 나오는 것을 볼 수 있다.
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 