素因数分解
素因数分解
自然数を素数だけの積で表すことを素因数分解といいます。
自然数を素数だけの積で表すことを素因数分解といいます。
[例]
12の素因数分解12＝2×2×3
【アルゴリズム】
60＝2×2×3×5という素因数分解を例にアルゴリズムを考えてみましょう。
[手順]
- 60は2で割れるかな？→割れた。→30になった。
- 30も2で割れるかな？→割れた。→15になった。
- 15も2で割れるかな？→割れない。
- じゃあ、3なら割れるかな？→割れた。→5になった。
- 5は3で割れるかな？→割れない。
- じゃあ、4なら割れるかな？→割れない。
- じゃあ、5なら割れるかな？→割れた。→1になった。→終わり。
[プログラム]
100 REM 素因数分解 110 INPUT PROMPT "n=":N 120 LET I=2 130 IF ＿＿＿＿＿＿＿＿＿＿＿＿＿＿ THEN 140 LET ＿＿＿＿＿ 150 IF ＿＿＿ THEN 160 PRINT I 170 GOTO 260 180 ELSE 190 PRINT I;"*" 200 GOTO 130 210 END IF 220 ELSE 230 LET ＿＿＿＿＿ 240 GOTO 130 250 END IF 260 END
[出力結果]
[設問1]
空欄を埋めてプログラムを完成させなさい。ただし、100行目のREM文はその後に続く文字列を無視する命令で、プログラム中にコメントを書くことができます。
[設問2]
このプログラムを実行し、変数Nに60を入力したとき130行目と140行目と230行目はそれぞれ何回ずつ実行されますか。また、変数Nに13を入れたときはそれぞれ何回ずつ実行されますか。
[設問3（発展）]
このプログラムを一部書き換え、nの素因数の集合P(n)を出力するようにしなさい。ただし、出力形式は次の例に従うこと。
(i) n=60の場合
P(60) = { 2, 3, 5 }
(ii) n=13の場合
P(13) = { 13 }