[백준 1929번] 소수 구하기 - 에라토스테네스의 체

 

- 제출 코드

import math
import sys
m, n = map(int, sys.stdin.readline().split())

def is_prime(x):
    if x==1:
        return False
    for i in range(2,int(math.sqrt(x)+1)):
        if x%i == 0:
            return False
    return True

while m<=n:
    if is_prime(m)==True:
        print(m)
    m += 1

소수를 구할때 반복문을 어디까지 돌릴지 생각해보면 3가지 경우가 존재한다. 

1. 2부터 해당 숫자까지

2. 2부터 해당 숫자를 2로 나눈 숫자까지

3. 2부터 해당 숫자에 루트를 씌운 숫자까지

큰 숫자의 범위에서 소수 여부를 판단할때 math.sqrt()를 반복해서 계산하는 시간이 여러 숫자를 더 계산하는 것보다 짧게 걸릴 것 같다는 생각에 3번을 사용했다.

 

기본적인 소수구하는 방법말고도 에라토스테네스의 체 방법을 사용해서 소수를 구할 수 있다. 

 

- 에라토스테네스의 체

 

아이디어 : 주어진 숫자 n까지 리스트를 만들고 2부터 숫자를 1씩 증가시켜나가며 2가 소수일경우 해당 숫자의 배수들을 뒤의 리스트에서 모두 지워준다

 

1. 1을 지워준다.

2. 2는 ( 지워지지 않음 )소수임으로 2의 배수들을 지워준다.

3. 3은 소수임으로 3의 배수들을 지워준다.

4. 4는 '2'번의 과정에서 지워져있다.

5. 5는 지워지지 않아 소수이다.

6. 6은 '2'번의 과정에서 지워져있다.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~의 반복이다.

 

소수들간의 수학적인 관계가 아직 밝혀지지 않았기 때문에 현재 가장 빠른 소수찾기 방법이라고 한다.

 

# 100까지
def is_prime(n):
    # 해당 수가 소수일 때 -> 뒤에 있는 해당 수의 배수들을 지워준다
    check_list = [False]+[False] + [True] * (n-1)
    for i in range(2,n+1):
        if check_list[i]==True: # 살아있으면 소수 -> 배수들을 지워주겠다
            for j in range(i*2, n+1, i):
                check_list[j] = False
    return [i for i in range(2, n) if check_list[i] == True]

print(is_prime(100))