Miller-Rabin 素数判定と Pollard-Rho 素因数分解
Miller-Rabin 素数判定
Miller-Rabin 法は、フェルマーの小定理と二次探査定理を組み合わせた確率的素数判定アルゴリズムです。以下の手順で動作します。
偶数および 0, 1, 2 は事前に判定します。
判定対象の奇数 n に対し、n - 1 = 2s × d（d は奇数）と分解します。
小さな素数 a を基底として選び、ad mod n を計算し、その後 s 回の平方と二次探査を行います。
最 ...
5月28日 04:02 投稿
素数和组合问题の解法
問題概要
与えられたn個の整数と整数k（k < n）があり、その中からk個の数を選んで和をとったときに、その和が素数になる組み合わせ数を求める問題。
例としてn=4, k=3で、数列が3,7,12,19のとき、選べる組み合わせは4通りある：
3+7+12 = 22
3+7+19 = 29
7+12+19 = 38
3+12+19 = 34
このうち素数は29のみなので、出力は1となる。
入出力形式
入力形式：
4 3 ...
5月14日 23:45 投稿