백준 1929번 문제 [python]

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1 복사

3 16

예제 출력 1 복사

3
5
7
11
13

---

실패한 풀이 1

M,N = map(int,input().split())
 
aaa = list(range(M,N+1))
bbb = []
sosu = []
for i in range(N):
    i+=1
    a = 1
    if i == 1:
        a = 0
    else:
        for j in sosu:
            if i % j == 0:
                a = 0
                break
    if a == 1:
        sosu.append(i)
for i in aaa:
    if i in sosu:
        print(i)

1. 소수를 담아둘 list를 만들고

2. 최댓값까지 for문을 형성하고

3. 소수 리스트에서 하나씩 꺼내서 for문의 i를 % 연산을 통해 소수인지를 판별하는 것

 

답은 맞았는데 시간 초과 떠버렸음 ㅋㅋ

 

---

 

실패한 풀이 2

M부터 N까지 리스트를 만들고

여기서 소수를 찾고 그 소수의 배수들을 전부 지워가는 식으로 했음

코드는 없는데 아무튼 시간초과뜸..

 

---

 

성공한 풀이

def sosu(aa,tmp_list):
    a = int(aa**0.5)+1
    standard = 0
    for i in range(a):
        i += 2
        standard = 1
        if aa % i == 0 and aa != i:
            standard = 0
            break
    if standard != 0:
        tmp_list.append(aa)
 
M, N = map(int,input().split())
result_list = []
if M == 1:
    for i in range(N-M):
        i += 2
        sosu(i,result_list)
else:
    for i in range(N-M+1):
        i += M
        sosu(i,result_list)
for i in result_list:
    print(i)

소인수분해를 이용해보고 해보았는데도 도저히 연산하는 양이 있는데 2초는 무리인 것 같아서 소수 관련해서 검색해봤더니 제곱근까지만 계산해도 된다고 했음

 

그래서 저거보다 더 복잡한 것으로 만들었는데 노트북에서 구동이 오래걸리길래 줄이고 줄이다보니 5초까지 줄였는데 아무리해도 2초가 안나옴 ㅋㅋ

 

근데 2초가 계속 어떻게 나오지?? 하고 백준에 제출했더니 성공했음