[수학] 백준 1929번 소수 구하기 with python

https://www.acmicpc.net/problem/1929
1번째 풀었던 방법

import math

start, end = map(int, input().split())
num = []
for i in range(start, end+1):
    if i != 1:
        num.append(i)
for i in range(2, int(math.sqrt(end))+1):
    j = 2
    while i*j <= end:
        if i*j in num:
            num.remove(i*j)
        j += 1
for n in num:
    print(n)

시간초과가 났다.
내가 생각하는 이유는 리스트.remove() 함수에서 난거 같다.
왜냐하면 remove는 앞에서부터 숫자를 순차적으로 찾아오기 때문에 O(N)의 시간복잡도를 갖는다.
N이 1억일 때 1초걸린다고 하면
숫자가 커졌을 때 for문도 O(N) remove도 O(N)이 되어 O(N^2)이 되므로 시간초과가 발생하는 것 같다.

import math

start, end = map(int, input().split())
num = [1]*(end+1)
num[0] = 0
num[1] = 0
for i in range(2, int(math.sqrt(end))+1):
    j = 2
    while i*j <= end:
        if num[i*j] == 1:
            num[i*j] = 0
        j += 1
for i in range(start, end+1):
    if num[i] == 1:
        print(i)

remove함수를 빼고 인덱스 자체로 접근하니 바로 해결되었다.
일단 이 문제의 키는 숫자 하나하나를 소수인지 아닌지 판별하는 것이 아닌 2의 배수를 없애고 3의 배수를 없애고 이런식으로 했을 때 남은 나머지 숫자가 소수다 라는 에라토스테네스의 체의 개념을 사용하여 풀면 되는 문제였다.