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년 전
계속해서 시간 초과가 나옵니다..
저는 아무리 생각해도 여기서 드라마틱 하게 더 줄일 방법이 떠오르질 않아요ㅠㅜ