python 백준 알고리즘 1929번: 소수 구하기

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

1929번: 소수 구하기

 

이전에 구했던 대로 소수 찾는 알고리즘을 사용했을 시에 시간초과가 뜨게 된다

num1, num2  = map(int, input().split())

for i in range(num1, num2 + 1):
    if i == 1:  # 1은 소수가 아니므로 제외
        continue
    for j in range(2, i):  # 2부터 i-1까지
        if i % j==0:  # 나누어 떨어지는 수가 있다면 break
            break
    else:
        print(i)

소수를 구하는 시간을 줄이는 방법을 찾아보니 두 가지 방법이 나왔다.

에라토스체네스의 체 - 가장 작은 소수의 배수부터 모두 지워나가는 방법

 

혹은

 

약수는 대칭이므로 ( ex) 16 의 약수 1,2,4,8,16 -> 1x16 , 2x8, 4x4, 8x2, 16x1 대략 제곱근을 기준으로 대칭 )

소수를 판별할때 특정수 -1까지가 아닌 특정수의 제곱근 까지만 검사를 하면 된다.

 

 

밑의 방식을 적용함

 

내 제출

num1, num2  = map(int, input().split())

for i in range(num1, num2 + 1):
    if i == 1:  # 1은 소수가 아니므로 제외
        continue
    for j in range(2, int(i**0.5)+1):  # 2부터 i의 제곱근 까지
        if i%j==0:
            break
    else:
        print(i)