課題 20170630-02 の考え方 「与えられた自然数の素因数を出力する」 -> 素因数分解を行う #「 数学的」に考える 手順 1. 具体例でやってみる 例 : 50 50 ... 素数である 2 で割り切れる 50 / 2 = 25 .. 2 25 ... 同じ素数である 2 で割り切れない、次に行く 25 ... 次の素数である 3 で割り切れない、次に行く 25 ... 次の素数である 5 で割り切れる 25 / 5 = 5 .. 5 5 ... 同じ素数である 5 で割り切れる 5 / 5 = 1 .. 5 1 は、これ以上、素因数は存在しないので、 これまでの素因数を並べて、終了 2 * 5 * 5 2. 一般化を行う 自然数 n が与えられたら n を小さい方の素数で割る 割り切れる限り、その素数で割る 割り切れない場合は、次の素数を試す もし、n が 1 になったら終了 !! 素数を、小さい方から、作る作業が必要 !! それだけでも、大変な内容 3. 「数学的な発想」 自然数の性質 m が n で割り切れて、n が p で割り切れれば、 m は、p 自身で割り切れる 例 : m=12, n=6, p=3 考察 今、p_1=2, p_2=3, ..., p_k が、小さい方からの素数の並び (定理1) 仮定:自然数 n が、p_1 から p_{k-1}までの素因数を持たない 結論:自然数 n は p_{k-1}+1 から p_k - 1 までの自然数で割り切れない why (証明) もし、自然数 n が p_{k-1}+1 <= m < p_k で割り切れたとする 定理 1 から、n は m の素因数で割り切れる 一方、m は、素数でないので、必ず、素因数 p_i を持つ p_i は、p_1 〜 p_{k-1} のいずれかなので、 これは、n が、p_1 〜 p_{k-1} までの素因数を持たない事に矛盾 背理法により、n は、p_{k-1}+1 <= m < p_k となる m で割り切れない 例: 50 50 / 2 -> o, 25, 2 25 / 2 -> x 25 / 3 -> x 25 / 4 -> x (かならず、割り切れない) (やっても、「無駄」だが、 論理上の悪影響はない） # プログラム上は、「遅く」なる # という悪影響はある 25 / 5 -> o, 5, 5 5 / 5 -> o, 1, 5 p_{k-1} わりきれなければ、次の素数である、 p_k を試す必要があるが、無駄と解っていても、 p_{k-1}+1 から p_k - 1 までを試しても、問題はない -> 素数で試すのではなく、自然数を順に試せばよい -> 「素数を小さいほうから並べる」課題は不要 [浮動小数点数] C 言語で標準で扱えるデータ構造の一つで、 実数(小数)を表現するデータ構造 型名は「double」を使う 小数の値を表現するために、小数点が利用できる 整数型と浮動小数点数の違い 整数型 浮動小数点数 宣言 int double 値の表現 数字列 小数点数を一つ含む数字列 例 : 123 123.456 -123 -123.456 四則 +,-,*,/ (共通) (割り算) 結果は整数 結果は浮動小数点数 小数点数以下は 小数点数以下も計算される 切り捨て 余りの演算子(%)がある ない 比較演算 (共通) ==, !=, <, >, <=, >= が使える 浮動小数点数では「==」はつかわない その代わりに、差の絶対値が小さい数より、 小さい場合を「等しいとみなす」 入出力 共通で、当分は s_input.h, s_print.h を利用 出力 s_print_int s_print_double 入力 s_input_int s_input_double 計算結果 正確に計算される 計算誤差が入る 本質的に無限なものを有限で表した結果 ライブラリ 共通で色々あるが.. 数学関数ライブラリがある 実数上の関数 sin, cos, exp, .. がある 5.0/3.0 = 1.666... (無限小数になる) 計算機では、「無限」は扱えない ある範囲で、切り捨て(四捨五入)がなされる 結果的に 1.66667 のようになる 計算に誤差が含まれる