エラトステネスの篩
問題
エラトステネスの篩を使って入力値以下の素数を求めましょう。
篩と書いて「ふるい」と読みます。難しいですね(2敗)
入力
・素数を求める範囲の最大値
・不適当な値が入力された場合、エラー落ちしてもいい
出力
・入力値以下の素数の数
・スペース区切りで、求めた素数のリスト
エラトステネスの篩
エラトステネスの篩 - Wikipedia
1) 求める範囲の最大値を20とします。
2) 2から始まる20までのリストを作ります
Prime list = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
3) リストの1番目の数「2」の倍数を削除します(2は残す)
Prime list = {2,3,5,7,9,11,13,15,17,19}
4) 次にリストの2番目の数である「3」の倍数を削除します(3は残す)
Prime list = {2,3,5,7,11,13,17,19}
5) 3番目の「5」は、20の平方根(4.472…)より大きいので操作を終了します
6) リストに残った数が20以下の素数です
例
素数を求める範囲の最大値を入力してください >100 素数25個 素数リスト 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
解答例
カプレカ数
問題
カプレカ数を計算してみよう。
入力
・3桁の整数値
・整数値以外、負の値の場合は再入力を求める
出力
・カプレカ操作の式
・式がループ状態になれば出力を止める
カプレカ数
・3桁で、同じ数字がない数(322や858、333等はだめ)を選ぶ
例として354の場合。
1) 数字を並び替え、最大値543と、最小値345を得る
2) 大きい数から小さい数を引き、
543-345 = 198
3) 答えの198に 1)と2)の操作を再び加える
891 - 198 = 643
4)以下、この操作を繰り返すと、ある値でループ状態になる
5)このループする値がカプレカ数
例
数値を入力してください(100 - 999) >154 541 - 145 = 396 963 - 369 = 594 954 - 459 = 495