success - Baekjoon 9단계-4 / 1929번 소수 구하기 python3

1929

 

처음엔 문제를 보고 시간제한도 2초길래

이전에 햇던 코드 조금만 변형하면 되지 않나? 라고 생각했었는데

 

ㅋㅋ

어림도없다!

 

그래서 기존 질문들을 뒤져보던 와중에

에라스토테네스? 의 체? 를 쓰면

큰수에서 획기적으로 시간을 줄일 수 있다고 해서

 

관련된 내용을 한번 찾아봤따

 

https://wikidocs.net/21638

2. 소수 구하기 - 에라토스테네스의 체

위키독스에 잘 나와있다

 

에라토스테네스였네 ㅋㅋ

 

위키독스 내용을 빌려오자면

 

1. 1은 제거

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.

3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.

4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.

5. (반복)

 

이정도가 되겠다.

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

대충 이런 코드라고 하는데

 

지금 이건 1부터 n까지의 에라토스테네스의 체여서

 

변형을 시키긴 해야겠다

 

 

 

....

 

 

지금 글 쓰면서 코드를 만지고 있는데

 

저거 왜 false false 가 들어가는거야??

 

0,1 을 제낀거냐 아니면

1,2 를 제낀거야 뭐 왜 저렇게된거임?

 

if a[i] 가 있는걸보니까 일단 2는 처음에 들어가야하고

그럼 0,1 을 제낀거같은데...

 

그럼 0,1 을 앞에 깔고 인덱스는 end + 1 이 되서 코드를 짜보면

 

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

def pn(n,m) :
    if n==1 : start=2
    else : start=n
    end=m

    a = [False,False] + [False]*(start-2) + [True]*(end-1-(start-2))
    #print(a)
    primes=[]
    for i in range(2,end+1):
      if a[i]:
        primes.append(i)
        for j in range(2*i, end+1, i):
            a[j] = False

    return primes
                
    
_n, _m=map(int, input().split())
pn_ls=pn(_n,_m)

for i in pn_ls :
    print(i)

 

뭐 이정도 될것 같고 주피터에서 잘 출력되서 백준에서 돌려보니까

 

이건또뭐...

 

print 주석처리 잘 했는데 뭐가 출력초과라는거지...?

라고하던 와중에 3 10 을 입력하니

3 4 5 7이 출력된다...

4는 왜거기 기어들어가있누...

 

a를 건드리는게 아니라 a리스트는 놔두고

이후 인덱스로 접근해봐야겠다

 

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

def pn(n,m) :
    start=n
    end=m

    a = [False,False] + [True]*(end-1)
    #print(a)
    primes=[]
    for i in range(2,end+1):
      if a[i]:
        if i>=start :
            primes.append(i)
        for j in range(2*i, end+1, i):
            a[j] = False

    return primes
                
    
_n, _m=map(int, input().split())
pn_ls=pn(_n,_m)

for i in pn_ls :
    print(i)

 

배열에 추가하는데만 조건문을 하나 더 달아줬는데

분명 시간소요가 더 되는건 아쉽지만

지금 시간? 점심시간 20분전 ㅋㅋ

빨리 포스팅 끝내버리고 밥 각

 

정답~

 

https://github.com/cyanindy/baekjoon_online_judge/blob/main/python3/step9/1929.py

GitHub - cyanindy/baekjoon_online_judge: https://www.acmicpc.net/