▼ 표 1.4.7 python3 primesieve.py 25의 트레이스
|
i |
isPrime[] |
|||||||||||||||||||||||
|
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
|
|
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
T |
|
2 |
T |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
F |
T |
|
3 |
T |
T |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
|
5 |
T |
T |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
F |
T |
F |
F |
|
|
T |
T |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
F |
T |
F |
T |
F |
F |
F |
T |
F |
F |
내포된 for 루프가 끝나면 소수가 아닌 isPrime[] 요소는 모두 False로, 소수인 isPrime[] 요소는 모두 True로 설정된다. factors.py에서 했던 것처럼 바깥 루프 종료 조건을 i * i >= n으로 설정할 수도 있지만, 이렇게 바꿔도 실행 속도는 별로 빨라지지 않는다. i가 n에 가까워질수록 if 조건이 거짓이 되므로 for 루프 안에서 실행할 코드가 전혀 없기 때문이다. 소수 여부를 모두 판별한 후에는, isPrime[] 배열을 한 번 더 훑어보면서 n보다 작거나 같은 소수의 개수를 모두 센다.
늘 그렇듯이 트레이스를 출력하도록 코드를 추가하는 것은 간단하다. primesieve.py와 같은 프로그램의 경우에는 약간 조심해야 하는데, for-if-for 구조로 내포되어 있으므로 트레이스 코드를 넣을 때 들여쓰기에 주의해야 한다.
primesieve.py로는 아주 큰 n에 대해서도 𝜋(n)을 구할 수 있는데, n은 파이썬이 허용하는 최대 배열 크기에 의해 제한된다. 이것은 공간-시간 타협의 또 다른 사례이다. primesieve.py같은 프로그램은 수학자들이 정수론을 개발하는 데 중요한 역할을 하며, 정수론은 암호학 등 중요한 분야에 응용되고 있다.