第6回

情報学基礎 II 小テスト No.6
1. 1,000,003 が素数であることを確かめるために,除数を 2, 3, 5, 7, 9, . . . として,
最初に 2 で割った後,奇数で試し割りしていき,元の数の平方根を超えない範
囲まで割っていくものとする.素数であった場合に必要な割り算の回数を,概
数で答えなさい.
2. 1,000,003 も 1,000,033 も素数であり,この 2 つの積は 1,000,036,000,099 で
ある.この数についても,上と同じアルゴリズムを使った場合の割り算の回数
の概数を答えなさい.
情報学基礎 II 小テスト No.6 解答用紙