【問題】Nが素数 (prime) であるか判定するプログラム
[プログラム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 SQR(N) STEP 2 30 IF N-I*INT(N/I)=0 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
[設問3（発展）]
プログラム3は、プログラム2を改良して処理の効率化（高速化）を図ったアルゴリズムである。このことについて説明しなさい。ただし、20行目と30行目の空欄は、それぞれプログラム2の20行目と30行目の空欄と同じ式が入ります。
[解答]
以下の点について指摘する。
- 13行目：2は素数である。
- 16行目：（2以外の）2の倍数は絶対に素数でないため、ループに入らないようにしている。
- 20行目：（2以外の）2の倍数は絶対に素数でないため、（2以外の）素数は奇数のみ調べればよいことになる。そこで、ループを"STEP 2"で回している。