情報学基礎 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 解答用紙