[BOJ:1929] 소수 구하기

문제

https://www.acmicpc.net/problem/1929

[

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

](https://www.acmicpc.net/problem/1929)

문제해결방법

• N이 소수인지 판별하기 위해서는 2부터 N의 반까지 N을 나누어 보면서 나누어 떨어지는 수가 있는지 확인하면 되기 때문에 O(N/2)의 시간복잡도가 걸린다.
  • 반까지만 나누어보면 되는 이유는 N의 반보다 큰수로는 절대로 나누어 떨어질 수 없다. 이유는 나누어 떨어진다는 것은 똑같이 나누어 준다는 것인데 반보다 더 큰 만큼 잘라서 한명에게 줬을 때 남은 수는 반보다 작은 수 즉 두 수는 같을 수 없게 된다. 결론적으로 똑같이 나누어 줄 수 없는 수 이다.
• 그런데 여러개의 수가 소수인지 판별하려면 각 수마다 O(N/2)의 시간복잡도가 걸리므로 확인하려는 수가 많은 수록 시간복잡도는 커지게 된다. 이럴 경우에는 에라토스테네스의 체를 이용하면 된다.
• 에라토스테네스의 체는 특정 수의 범위에서 구하고자 하는 수의 구간을 나열하고 소수가 아닌 수를 지워나가는 것인데 어떻게 소수가 아닌 수를 지우는지는 아래와 같다.
• 2는 소수이므로 남겨두고 2의 배수를 지운다. 왜냐하면 2의 배수는 2로 나누어떨어지기 때문에 소수가 아니다. 다시 남아 있는 수 가운데 3은 소수이고 3의 배수를 지운다. 다시 남은 수 가운데 다음수는 5이다. 4는 2의 배수로 지워졌기 때문이다. 그렇게 5는 소수이고 5의 배수를 지운다. 이 과정을 구간내에서 반복하면 소수만 남게 된다.

코드

import sys

start, end = map(int, sys.stdin.readline().rstrip().split())

primeCheck = [True]*(end+1)
primeCheck[0] = False
primeCheck[1] = False

for i in range(2,end+1):
    for j in range(i+i,end+1,i):
        primeCheck[j] = False

for k in range(start, end+1):
    if primeCheck[k]:
        print(k)