프로그램 1.4.3 에라토스테네스의 체 (primesieve.py)

import sys
import stdarray
import stdio
 
n = int(sys.argv[1])
 
isPrime = stdarray.create1D(n+1, True)
 
for i in range(2, n):
    if (isPrime[i]):
        # i의 배수 인덱스 요소들은 모두 소수가 아니라고 표시한다.
        for j in range(2, n//i + 1):
            isPrime[i*j] = False
 
# 소수의 개수를 센다.
count = 0
for i in range(2, n+1):
    if (isPrime[i]):
        count += 1
stdio.writeln(count)

n
isPrime[i]
count

인수
i가 소수인가?
소수 카운터

이 프로그램은 명령 줄 인수로 n을 입력받고 n보다 작거나 같은 소수의 개수를 계산한다. i가 소수이면 isPrime[i]를 True, 아니면 False로 설정해 소수의 개수를 센다.

% python3 primesieve.py 25
9
% python3 primesieve.py 100
25
% python3 primesieve.py 10000
1229
% python3 primesieve.py 1000000
78498
% python3 primesieve.py 100000000
5761455