Miller-Rabin判素法
身败名裂的阮行止这篇文章出错了。 注意下面介绍的算法只是伪素数测试 给定一个数 n n ，判断它是否是 质数 。 n < = 2 × 10 9 n <= 2 × 10 9 . 回顾以前判断素数的办法。我们把 n n 在 [ 1 , √ n ] [ 1 , n ] 的范围内试除，看是否有数能整除 n n 。算法的时间复杂度是 O ( √ n ) O ( n ) 的。这里跑不过。 费马小定理 ∀ n ∈ Z + ∀ n ∈ Z + 、 p p 为质数，有 n p ≡ n ( mod p ) n p ≡ n ( mod p ) . 更一般的 欧拉定理 ： ∀ gcd ( p , n ) = 1 ∀ gcd ( p , n ) = 1 ，有 n φ ( p ) ≡ 1 ( mod p ) n φ ( p ) ≡ 1 ( mod p ) . 考虑费马小定理的 逆命题 。 若 n p ≡ n ( mod p ) n p ≡ n ( mod p ) ，则 p p 为质数。 这个命题显然是错的，但是它 几乎 成立。因此我们可以用它来判定素数。 伪素数判断 随机选择 x x ，如果 x n ≢ x ( mod n ) x n ≢ x ( mod n ) ，那么 n n 肯定不是质数。 因为有可能出错，所以我们选择 多个底数 来测试。如果所有的测试都认为 n n 是质数，那么我们就认为它是质数。 这样写： bool is_prime ( int x ) { int i , x ; for ( i = 0 ; i < lambda ; i ++ ) { x = rand () % n + 1 ; if (( pow ( x , n ) % n ) != x ) return 0 ; //发现不符合 } return 1 ; } lambda是测试次数。这个东西设为多少看数据范围。 最终代码： #define lambda 233 long long pow ( long long a , long long b , long long mod ) {...