글 읽기 - 에라토스테네스의 체를 이렇게 구현하는게 맞는지 모르겠네요ㅠㅠ(파이썬)

minsu8502 5년 전 0

저 나름의 방식으로 효율적으로 했다고 생각하는데 8번이상 시간초과가 나오네요ㅠㅠ

시간 측정해보니 에라토스는 얼마 안걸리는 것 같은데

이렇게 푸는게 아닌건가요?? 고수님들 가르침을 받고 싶어요!! 파이썬 입문자입니당

import bisect

def is_prime(n:int) -> [int]: #에라토스테네스의 체(소수구하기)
    seive=[False,False]+[True]*(n-1) # k의 배수를 지우는 방식으로 구현됨
    l=round(n**0.5)+1 #루트 n까지만 반복문을 수행()
    for k in range(2,l):
        if seive[k]:
            seive[k*2::k]=[False]*((int)(n/k)-1)
    seive[2]=False # 2는 "짝수인소수" 이기때문에 이 문제에서는 제외
    return [x for x in range(1,n,2) if seive[x]]# (n+0)은 답으로 불가능하기때문에 n번 인덱스는 제외하고 return

flag=1
prime_number=is_prime(1000001)
while 1:
    N = int(input())
    if N==0:
        break
    for i in range(N):
        temp=N-prime_number[i]
        ans=bisect.bisect_left(prime_number,temp,lo=i,hi=len(prime_number))
        if ans>=len(prime_number):
            continue
        if (prime_number[i]+prime_number[ans])==N:
            flag=0
            print(N,"=",prime_number[i],"+",prime_number[ans])
            break          
    if flag:
        print("Goldbach's conjecture is wrong.")

jh05013 5년 전 1

https://www.acmicpc.net/proble...

minsu8502 5년 전 0

감사합니다 해결했습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

에라토스테네스의 체를 이렇게 구현하는게 맞는지 모르겠네요ㅠㅠ(파이썬)

minsu8502 5년 전 0

jh05013 5년 전 1

minsu8502 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말