수학

에라토스테네스의 체

소수를 체로 거르기

1부터 60까지 수가 있습니다. 몇 개가 남을지 먼저 고르고 지워지지 않은 가장 작은 수를 눌러 그 수의 배수를 지워 보세요.

남은 수는 더 작은 수의 배수가 아니다

• 지워지지 않은 수 — 더 작은 어떤 수의 배수도 아니다. 그래서 1 과 자기 자신 말고는 약수가 없다
• 작은 수부터 누른다 — 앞에서 누른 수가 합성수를 대신 지워 준다. 3 을 누르기 전의 9 는 아직 지워지지 않았을 뿐 약수가 3 인 수다
• 처음부터 지워 둔 1— 약수가 1 하나뿐이라 “1 과 자기 자신” 규칙에서 따로 뺐다

코드는 소수를 만날 때마다 배수를 지운다

위에서 지운 것과 같은 1~60 입니다. is_prime[k] 가 True 인 수가 지워지지 않고 남은 수입니다.

다음을 눌러 한 줄씩 넘기며 지워지는 칸을 보세요. 안쪽 반복은 칸마다 되풀이되지만 소수 하나당 두 스텝으로 묶어 보여 줍니다.

• if is_prime[i] — i 가 아직 지워지지 않았을 때만 안쪽 반복으로 들어간다
• range(i * i, n + 1, i) — i × i 부터 i 칸씩 지운다. i × 2 부터 i × (i − 1) 까지는 더 작은 수가 이미 지웠다
• int(n ** 0.5) — i 는 7 까지만 돈다. 8 부터는 i × i 가 60 을 넘어 새로 지울 수가 없다

체에서 틀리는 자리

• is_prime[0] = is_prime[1] = False 를 빼면 — 에러가 안 난다. 소수 목록이 17개가 아니라 19개이고 [0, 1, 2, …] 로 시작한다
• i * i 대신 i * 2 부터 지우면 — 결과는 같다. 지우는 횟수만 늘어서 100만 기준 2,122,048번 대 2,197,839번이다. 시간은 0.035초와 0.036초로 거의 같았다
• 바깥 반복을 n 까지 돌리면 — √n 보다 큰 수까지 전부 훑는다. 100만에서 999번이 아니라 999,999번 돈다. 0.035초가 0.049초가 됐다
• 수 하나만 소수인지 알고 싶으면 — 체를 만들 필요가 없다. √n 까지 n % d 로 나눠 보면 된다. 1,000,000,007 은 0.0013초 만에 소수라고 나왔다
• 칸이 많으면 메모리가 문제다 — 리스트는 한 칸이 8바이트라 100만 칸이 8,000,056바이트(sys.getsizeof)다. 1억 칸이면 약 800MB다. bytearray 는 한 칸 1바이트라 약 100MB다
• 슬라이스로 한 번에 지우면 — is_prime[i*i::i] = [False] * len(range(i*i, n+1, i)). 1000만에서 0.55초가 0.22초로 줄었다

문제에서 이 말이 보이면

이 탭의 알고리즘 목록은 여기까지입니다. 왼쪽 사이드바에서 다른 장을 골라 다시 풀어 보세요.