글 읽기 - 이게 왜 시간초과인가요.. 아무리봐도 시간복잡도는 n인데..(PyPy3)

johnkoh1107 2년 전 0

에라토스테네스도 nlogn 미만인걸로 알고있고 n^2 이상을 쓴거같지는 않은데..

def eratos(n):
    prime=[0 for i in range(n+1)]
    prime[0]=1
    prime[1]=1
    for i in range(2, n+1):
        if prime[i]==0:
            for j in range(i**2, n+1, i):
                prime[j]=1
    return prime
l, u=map(int, input().split())
primecount=0
prime4count=0
while(l!=-1 or u!=-1):
    if u<=1:
        print(l, u, 0, 0)
    else:
        if l<0:
            lp=l
            l=0
            up=u
        lp=l
        up=u
        primecount=0
        prime4count=0
        primeset=eratos(u)
        for i in range(l, u+1):
            if not primeset[i]:
                primecount += 1
                if i%4==1:
                    prime4count += 1
        print(lp, up, primecount, prime4count)
    l, u=map(int, input().split())

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

문제

문제

출처

ICPC

이게 왜 시간초과인가요.. 아무리봐도 시간복잡도는 n인데..(PyPy3)

johnkoh1107 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말