backsung75   1년 전

계속해서 시간 초과가 나옵니다..

저는 아무리 생각해도 여기서 드라마틱 하게 더 줄일 방법이 떠오르질 않아요ㅠㅜ

hych0502   1년 전

list_.remove(i)를 통해 소수가 아닌 수를 지우는 게 시간복잡도가 O(n)이라 너무 느립니다.

list를 작성할 때 0과 1로 소수를 체크할 수 있도록

list_ = [1 for i in range(2, m + 1)]

과 같이 작성하고 소수가 아닌 수를 0으로 만드는 방법을 추천드립니다.

(list[숫자] 의 값이 1: 숫자가 소수, 0: 합성수)

또 소수를 뺄때

for i in range(z * 2, m + 1, z):

처럼하면 z의 배수로만 for문이 동작하기 때문에 더 빠르게 소수를 찾을 수 있습니다.

backsung75   1년 전

해결 되었습니다 감사합니다!!

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