[python]1929.소수 구하기

 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하는 문제인데 솔직히 알고리즘 시간에 배워서 별 생각이 없었다. 

아무생각없이 풀다가 시간초과났다.

이럴거면 문제에 일반적으로 소수를 구하는 알고리즘을 구현하다가는 시간초과딱밤을 맞게 될거라고 말좀 해주던가.

이게 시간초과 코드

 

m,n = map(int, input().split()) #정수 입력
 
for i in range(m, n+1):
    if i==1:
        continue
    if i==2:
        print(i)
    else:
        for j in range(2, i):
            if i%j==0:
                break
            if j==i-1:
                print(i)
                

 

아무생각없이 해당 숫자까지 나누기로 구하다가는 큰코다친다.

다른 블로그 글 봤는데 에라토스테네스 체?를 사용하던데 그러지 않아도 된다, 이 문제에선.

해당 숫자가 소수인지를 판별하는 방법은 2부터 그 숫자까지 나누기를 계속해서 나머지가 0인 적이 없었던 숫자를 소수라고 판단하는 방법도 있지만 해당 숫자의 제곱근까지 나누기를 해서 나머지가 0인적이 있는지 없는지해서 소수를 판별할 수도 있다. 

 

import math
def primeop(num):
    if num==1:
        return False
    if num==2:
        return True
    else:
        for j in range(2, int(math.sqrt(num))+1):
            if num%j==0:
                return False
        return True
 
m,n = map(int, input().split()) #정수 입력
for i in range(m, n+1):
    if primeop(i):
        print(i)

 

www.acmicpc.net/problem/1929