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

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

 

문제 

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

 

사용언어 : python3

 

이 문제를 그냥 풀었는데, 몇 번을 시도해보았지만 "시간초과"가 떴다.

초기 코드

num = list(map(int,input().split()))
for a in range(num[0],num[1]+1):
    count =0
    if a > 1:
        for b in range(1,a+1):
            if a % b ==0:
                a+=1
        if count ==2:
            print(a)

 

 

시간을 줄이기 위해서 리스트를 만든 다음

리스트를 제외해 가면서 풀어 보았다.

다음 코드는 정답 코드

import math

def Solution(num):
    if num ==1:
        return False
    for a in range(2,int(math.sqrt(num))+1):
        if num / a == 1:
            break
        elif num % a == 0:
            return False
    return True

num1,num2 = map(int,input().split())
for a in range(num1,num2+1):
    if Solution(a) ==True:
        print(a)