素数

素数

【問題】Nが素数 (prime) であるか判定するプログラム

[プログラム1]

　　10  INPUT PROMPT "n=":N
　　20  FOR I=2 TO N-1
　　30      IF ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ THEN
　　40          PRINT N;"is not a prime."
　　50          GOTO 90
　　60      END IF
　　70  NEXT I
　　80  PRINT N;"is a prime."
　　90  END

[設問1]

　空欄を埋めてプログラム1を完成させて実行しなさい。ただし、30行目の空欄には「NがIで割り切れる。」という条件文が入ります。

[解答1]

[解説1]

　設問1で確認したように、プログラム1はNが素数であるか正しく判定することができます。しかし、プログラム1にはいくらか無駄があります。

　その1つとして、実際には2〜N-1の自然数で割り切れるかどうか確かめなくてもNが素数であるか判定できることがあげられます。素数の性質1から、2〜の自然数で割りきれるかどうか確かめるだけでよいのです。

　そこで、プログラム1を書き換え、プログラム2としました。

[プログラム2]

　　10  INPUT PROMPT "n=":N
　　20  FOR I=2 TO ＿＿＿＿＿＿
　　30      IF ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ THEN
　　40          PRINT N;"is not a prime."
　　50          GOTO 90
　　60      END IF
　　70  NEXT I
　　80  PRINT N;"is a prime."
　　90  END

[設問2]

　空欄を埋めてプログラム2を完成させなさい。その後、実行してプログラム1と同様に正しく動作することを確認しなさい。ただし、30行目にはプログラム1と同じ条件文が入ります。

[解答2]

[プログラム3]

　　10  INPUT PROMPT "n=":N
　　13  IF N=2 THEN GOTO 80
　　16  IF N-INT(N/2)*2=0 THEN GOTO 40
　　20  FOR I=3 TO ＿＿＿＿＿＿ STEP 2
　　30      IF ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ THEN
　　40          PRINT N;"is not a prime."
　　50          GOTO 90
　　60      END IF
　　70  NEXT I
　　80  PRINT N;"is a prime."
　　90  END

※掲載していたプログラムに間違いがあったため、2009/8/2に修正しました。申し訳ございませんでした。

[設問3（発展）]

　プログラム3は、プログラム2を改良して処理の効率化（高速化）を図ったアルゴリズムである。このことについて説明しなさい。ただし、20行目と30行目の空欄は、それぞれプログラム2の20行目と30行目の空欄と同じ式が入ります。

[解答3]