[BOJ] 1929 | 소수 구하기

 

1929 | 소수 구하기
https://www.acmicpc.net/problem/1929

 

 

 

작성 코드

 

import math


N, M = map(int, input().split())
for n in range(N, M+1):
    dec = True
    if n == 1:
        continue
    for i in range(2, int(math.sqrt(n))+1):
        if n%i == 0:
            dec = False
            break
    if dec:
        print(n)

 

• 범위를 제곱근으로 지정함으로써 시간 초과 해결

 

 

이상 코드

 

에라토스테네스의 체

 

m, n = map(int, input().split())
n += 1                            
prime = [True] * n   

for i in range(2, int(n**0.5)+1):
    if prime[i]:                    
        for j in range(2*i, n, i):   
            prime[j] = False

for i in range(m, n):
    if i > 1 and prime[i] == True:  
        print(i)

 

• 소수는 1과 자기 자신을 제외한 약수를 가지면 안 됨 -> 배수 제거 

 

 

제곱근으로 나누는 이유

 

약수는 제곱근 기준으로 대칭이 일어나기 때문입니다

제곱근 이후의 약수들은, 제곱근 이전의 약수들과 매칭이 됩니다