백준 1929 파이썬 (소수 구하기)

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

💻 Code

n, m = map(int, input().split())
ans = []
for num in range(n,m+1):
    if(num == 1):
        continue
    for i in range(2,num):
        if(num % i == 0):
            break
    else: ans.append(num)

for i in ans:
    print(i)
    

1. 1일경우 소수가 아니므로 continue
2. 2부터 나눠지는 수가 1과 자기 자신 뿐이라면 ans에 append
3. 불필요한 계산을 피하기 위해 나누어 떨어지는 수가 있다면 중간에 break해주었다.

그러나 시간초과..
n과 m의 범위가 1~1,000,000 인것에 비해 시간제한이 2초 밖에 안됐었다

🎯   에라토스테네스의 체

소수를 구하는 알고리즘으로 O(n log(logn))의 시간복잡도를 가진다.

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)

파이썬 코드로 옮기면 다음과 같다

n=10
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

# primes = [2, 3, 5, 7]

다시 문제로 돌아가서 풀어보자

n,m = map(int,input().split())

# 에라토스테네스의 체 초기화 : n개 요소에 True 설정 (소수로 간주, 0과 1 제외)
sieve = [False, False] + [True] * (m-1)
limit = int(m ** 0.5)

for i in range(2, limit+1):
    if sieve[i] == True: # i 가 소수인 경우
        for j in range(2*i, m+1, i): # i 이후 i의 배수는 False로 판정한다.
            sieve[j] = False
# 만들어진 소수 목록 산출 
primes = [i for i in range(2,m+1) if sieve[i]== True]

for prime in primes:
    if prime >= n:
        print(prime)

1. 0, 1 은 False, 나머지는 True
2. i = 판별할 수, j는 나눠주는 수
3. 범위는 2부터 (m**0.5) + 1 까지
   ex) 12일 경우 12의 제곱근은 3
   12의 약수가 1 2 3 4 6 12 이고
   4 6 12 는 대칭되는 수의 배수이므로 제외한다.
4. 에라토스테네스의 체 알고리즘을 적용하여 배수는 지워나간다

이 문제에서 포인트는 빨간색으로 표시한 범위가 아닌가 싶다. (이걸 어케 생각하지)
아무튼 제곱근 구할때 앞으로는 **0.5로 구하자 (1/2 제곱이라고 생각)

출처 : https://wikidocs.net/21638 (에라토스테네스의 체)