이제는 에라토스테네스의 체🔥

사견

에라토스테네스의 체가 여러개의 숫자가 소수인지 확인할때 시간을 단축해준다는건 알고 있었다. 하지만 딱봤을때 코드가 깔끔하다고 느껴지지 않아서 잘 손이 안 갔는데...이 기회를 빌어 확실히 하고 넘어가야겠다.

아 근데 저 False, True로 소수 확인 그래프를 만드는건 진짜.... 비주얼적으로 취향이 아님

개념

#1을 제거한다
#현재 가장 작은 수인 2를 소수로 두고 나머지 2의 배수를 제외한다
#남은 수중 가장 작은 수인 3를 소수로 두고 나머지 3의 배수를 제외한다
#반복한다.

코드

n=1000
a = [False,False] + [True]*(n-1)
#0부터 n까지의 그래프를 만든다. 이중에서 0과1은 소수가 아니니 false로 두고 나머지는 일단 디폴트값 True를 부여한다.
prime=[]

for i in range(2,n+1): #2부터 n까지 for문을 돈다
  if a[i]: #for 문을 돌때마다 True값이 나온 첫번째 i를 소수라 생각하고 다음을 진행한다.
    prime.append(i) #먼저 소수 리스트에 어팬드 한다.
    for j in range(2*i, n+1, i):#2i부터 시작하는 배수들을 False로 지정한다
        a[j] = False
print(prime)