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

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

예전 도전(실패)- 문제 풀이

예전에 풀 때는 N 이하 소수를 찾아서 리스트 S 안에 넣고, 나중에 S에서 M 미만의 소수를 제거했다. 그리고 S의 값을 출력했다. 그랬더니 시간 초과가 나왔다.

예전 도전(실패)- 코드

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

# N이하 소수 찾기-> 리스트 S에 넣기
S=[2,3]
for i in range(4, N+1):
    if i%2==1:
        for j in range(len(S)):
            if i % S[j] ==0: break
            else:
                if j==len(S)-1: S.append(i)

# M이상 N이하 소수 찾기
for o in S:
    if M<=o: continue
    else: S.remove(o)

for p in S:
    print(p)

오늘 1차 도전(실패)- 문제 풀이

에라토스테네스 체 방법을 공부하고 신나게 풀었다..
에라토스테네스 체 방법으로 N 이하의 소수를 구해서 sosu 리스트에 넣었고, M 이상 N 이하의 수 중에서 sosu에 있으면 출력했다.
그러나 또 시간 초과..

오늘 1차 도전(실패)- 코드

M,N=map(int,input().split()) #입력받음

#에라토스테네스 체 방법으로 N 이하의 소수 구해서 sosu 리스트에 넣음
L=[0]*(N+1)
sosu=[]
for i in range(2,N+1):
    if L[i]==0:
        sosu.append(i)
        for j in range(i,N+1,i):
            L[j]=1

#M 이상 N 이하 수 중에서 sosu에 있으면 출력
for j in range(M,N+1):
    if j in sosu:
        print(j)

오늘 2차 도전(성공)-문제 풀이

그러다가 드디어 성공!!
에라토스테네스 체 방법으로 M 미만의 소수를 구하고, 그 소수의 배수(N 이하)를 없애줬다. 이 소수들은 따로 저장해두지는 않았다. 어차피 출력할 필요가 없으니까.
그리고 M 이상 N 이하의 소수를 구해서 sosu 리스트에 넣었다. 마지막으로 sosu 리스트의 값을 하나씩 출력해주면 끝!
마지막까지 고민했던 부분은 L[1]을 1로 대입해주는 것!
이걸 하지 않았더니 M이 1일 때 문제가 생겼다.
for i in range(M,N+1) 부분에서, for i in range(1,N+1)이 되어버린 것이다. 그러면 1은 소수가 아닌데, sosu 리스트에 들어가버리게 된다.

오늘 2차 도전(성공)- 코드

M,N=map(int,input().split()) #입력받음
L=[0]*(N+1)
L[1]=1 #이거는 나중에 추가함 -> M이 1일 때 문제 생겨서
sosu=[]
#에라토스테네스 체 방법으로ㅡ 2이상 M 미만의 소수를 구하고, 그 소수의 배수들을(N 이하) 없애줌
for i in range(2,M):
    if L[i]==0:
        for j in range(i,N+1,i):
            L[j]=1

for i in range(M,N+1): #M 이상 N 이하의 소수 구해서 sosu 리스트에 넣기
    if L[i]==0:
        sosu.append(i)
        for j in range(i,N+1,i):
            L[j]=1

for k in sosu: #출력
    print(k)