javascript求一个数是否为质数，验证质数的方法
javascript求一个数是否为质数，验证质数的方法function square(x) { return x * x; } function is_even(n) { return n % 2 === 0; } function expmod(base exp m) { return exp === 0 ? 1 : is_even(exp) ? square(expmod(base exp / 2 m)) % m : (base * expmod(base exp - 1 m)) % m; } function random(n) { return Math.floor(Math.random() * n); } function fermat_test(n) { function try_it(a) { return expmod
研讨会上的一群人Group of people at the seminar
本文将描述两种验证质数的方法，一种的增长率为 另外一种为probabilistic algorithms其增长率为logn.
寻找因子寻找因子的方法简单而直接，从整数2开始，连续测试能否被整除，就是寻找第一个因子。
function square(x) {
return x * x;
}
function smallest_divisor(n) {
return find_divisor(n 2);
}
function find_divisor(n test_divisor) {
return square(test_divisor) > n ? n
: divides(test_divisor n) ? test_divisor
: find_divisor(n test_divisor 1);
}
function divides(a b) {
return b % a === 0;
}
smallest_divisor(42);
验证是否为质数，只需要验证，n是否与其最小的因子相等。
function is_prime(n) {
return n === smallest_divisor(n);
}
函数find_divisor的最终测试条件，基于这样的事实，即如果n不是素数，那么它必然有因子小于或者等于 因此，我们的算法只需要验证1和之间的整数即可。因此，算法所执行步骤的增长率就是.
费马小定理另外一种 乃是基于费玛小定理： 假如a是一个整数，p是一个質数，那么
实现的算法如下：
function is_even(n) {
return n % 2 === 0;
}
function square(x) {
return x * x;
}
function expmod(base exp m) {
return exp === 0 ? 1
: is_even(exp) ? square(expmod(base exp / 2 m)) % m
: (base * expmod(base exp - 1 m)) % m;
}
expmod(4 3 5);
这与之前的fast_expt方法极为相似。
function square(x) {
return x * x;
}
function is_even(n) {
return n % 2 === 0;
}
function expmod(base exp m) {
return exp === 0
? 1
: is_even(exp)
? square(expmod(base exp / 2 m)) % m
: (base * expmod(base exp - 1 m)) % m;
}
function random(n) {
return Math.floor(Math.random() * n);
}
function fermat_test(n) {
function try_it(a) {
return expmod(a n n) === a;
}
return try_it(1 random(n - 1));
}
console.log(fermat_test(97));
最后设置验证的次数。
function fast_is_prime(n times) {
return times === 0 ? true
: fermat_test(n) ? fast_is_prime(n times - 1)
: false;
}
