[Python] Baekjoon 백준 1929번 소수 구하기

[Python] Baekjoon 백준 1929번 소수 구하기

 

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

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

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

def cal(a):
    if a == 1:
        return False
    else:
        for i in range(2, int(a ** 0.5) + 1):
            if a % i == 0:
                return False
        return True

a, b = map(int, input().split())

for i in range(a, b + 1):
    if cal(i):
        print(i)

 

무식하게 그냥 했다가 시간초과를 맛보았다...

 

중요포인트는

소수를 확인하기 위해 어디까지 반복문을 돌려볼것인가 이다

결론은 제곱근 +1 까지만 돌려보면 된다

 

제곱근 구하는 방법

math.pow(x, .5)

math.sqrt(x)

x ** 0.5

 

주의. 반환 타입은 float 이다

 

 

추가

에라토스테네스의 체

: 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

에라토스테네스의 체 를 Python 으로 구현

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]