(Python/🥈3)백준 알고리즘 1929번: 소수 구하기

문제 출처:https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

틀린 풀이:

M,N = input().split()
M = int(M)
N = int(N)   # M,N = map(int,input().split())
	
for i in range(M,N+1):  #3부터 16까지
    if i != 1:
        for k in range(2,i):
            if i % k ==0:
                break
        else:
            print(i)

 

처음에 이렇게 작성해서 답은 나오지만 시간초과가 나왔다. 이중포문을 사용해 빅오가 O(n^2)라 그런것 같다.

100만 제곱이니까..

 

풀이:

M,N = input().split()
M = int(M)
N = int(N)
for i in range(M,N+1):
    if i == 1:
        continue
    for j in range(2,int(i**(1/2))+1):  # 제곱근
        if i % j == 0:
            break
    else: print(i)

똑같은 이중 포문이지만 j의 범위가 100만이 아니라 시간초과는 나오지 않는다.

 

해당 수의 제곱근까지 나눠보는 이유는 약수는 대칭으로 이루어져있다.

예를들어

15 는 1,3,5,15  /  1*15  , 3*5 

25는 1, 5, 25   / 1*25 , 5*5 

 

즉 제곱근 보다 같거나 작은수까지만 나눠보면 된다.