[python 파이썬] 백준 1929번: 소수 구하기

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

1929번: 소수 구하기

 

 

 

 

 

처음 코드:

 

M, N = map(int, input().split())
arr=[]

for i in range(M,N+1):
    if i==1:
        pass
    elif i==2:
        arr.append(i)
    else:
        for j in range(2, i):
            if i%j==0:
                break
            elif j==i-1:
                arr.append(i)

for i in arr:
    print(i)

 

처음에는 하나씩 검사하고 리스트에 넣어서 마지막에 리스트를 출력했더니 시간 초과가 떴다.

그래서 다른 블로그들을 찾아보니 함수를 사용하고, 소수인지 검사할때 2부터 i까지 검사하는 것이 아니라 2부터 i의 제곱근까지만 검사하면 나머지는 검사하나 마나여서 제곱근까지만 검사하면 되는 것이었다.

수정한 코드:

 

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

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

for i in range(M, N+1):
    if isPrime(i):
        print(i)

 

소수인지 검사해주는 isPrime함수를 정의해서 2부터 num의 제곱근까지 검사하여 소수인지 판별하여 소수이면 출력되도록 했다.