67. 1929(소수 구하기)

import math
M, N = map(int, input().split())

for i in range(M, N+1):
    if(i == 2 or i == 5):
        print(i)
        continue

    index = i % 10

    if((index == 1 or index == 3 or index == 7 or index == 9) and i != 1):
        is_prime = True
        R = int(math.sqrt(i))
        for j in range(2, R+1):
            if(i % j == 0):
                is_prime = False
                break

        if(is_prime):
            print(i)

시간제한이 있어 많이 생각해야 하는 문제.

 

소수에 대한 팁 :

1. 10이상 부터 소수는 일의자리가 1,3,7,9에만 분포되어 있다.

2. 값의 제곱근 이상의 수로는 나눌 수 없다.

3. 제곱근값 이내에서 1을 제외하고 한번이라도 나눠진다면 소수가 아니다.

 

 

소수 목록을 정리해놓은 사이트

https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 

소수 (수론) - 위키백과, 우리 모두의 백과사전