글 읽기 - 파이썬 시간초과 도와주세요ㅠ

agsf1423 3년 전 0

로직은 잘 구현된 것 같은데

시간을 어떻게 줄일 수 있을까요ㅠ

# 에라토스테네스의 체
M, N = map(int, input().split())
primes = list(range(2, N+1))
for i in range(N+1):
    if primes[i] ** 2 > N:
        break
    for j in range(2, N+1):
        try:
            primes.remove(j*primes[i])
        except:
            pass
for i in primes:
    if i >= M:
        print(i)

suker80 3년 전 1

리스트의 remove는 O(N)시간 걸리는 명령어입니다

시간복잡도는 O(N^3)이구요

이걸 사용하지말고 길이만큼 리스트를 1로 선언하고 소수가 아닌 것들은 0으로 초기화하시면서 하면 더빠를거예요

agsf1423 3년 전 0

덕분에 해결했습니다! 감사합니다.

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

문제

문제

출처

ICPC

파이썬 시간초과 도와주세요ㅠ

agsf1423 3년 전 0

suker80 3년 전 1

agsf1423 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말