글 읽기 - 에라토스테네스의 체를 써도 시간초과가 납니다...

wjsalsdn16 2년 전 0

체를 써도 시간초과가 나는건 왤까요?

while True:
    a = int(input())
    if a != 0:
        b = 2*a
        x = [False,False]+[True]*(b-1)
        primes = []
        result = []

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

        for k in range(len(primes)):
            if primes[k] >= a+1:
                result.append(primes[k])

            else:
                continue;

        print(len(result))
       
    else:
        break;

djm03178 2년 전 1

에라토스테네스의 체는 처음에 한 번만 하면 됩니다. 매 케이스마다 하면 비효율적입니다.

wjsalsdn16 2년 전 0

이게 시간초과가 될정도로 무리가 가는군요... 덕분에 해결했습니다 감사함당

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

문제

문제

출처

ICPC

에라토스테네스의 체를 써도 시간초과가 납니다...

wjsalsdn16 2년 전 0

djm03178 2년 전 1

wjsalsdn16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말