소수 - 백준 1929 [Python]

소수의 조건

• 약수가 1과 자기 자신 밖에 없는 수
• N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

소수를 구하는 방법

1. 어떤 수 N이 소수인지 아닌지?
2. N이하의 모든 소수를 구하는 방법

2. N이하의 모든 소스를 찾는 방법 : 앞서 말한 1번과정과 비슷하게 문제풀이를 한다면 N루트N의 시간복잡도가 발생한다. 이때 에라토스테네스의 체를 활용하면 더 빠르게 풀 수 있다.

• 2부터 N까지 모든 수를 써놓는다.
• 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
• 그 수는 소수이다.
• 이제 그 수의 배수를 모두 지운다.

이 문제를 해결하기 위해선, 2개의 배열이 필요하다.

• 수를 지웠는지 아닌지 [T/F]
• 소수의 목록을 유지할 배열

 

Example)

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

1929번: 소수 구하기

 

Solution)

MAX = 1000000
check = [0]*(MAX+1)
check[0] = check[1] = True

for i in range(2, MAX+1):
    if not check[i]:
        j = i+i
        while j <= MAX:
            check[j] = True
            j += i
n, m = map(int, input().split())

for i in range(n,m+1):
    if not check[i]:
        print(i)