Difference between revisions of "Testing for prime"
Jump to navigation
Jump to search
Line 49: | Line 49: | ||
}) | }) | ||
); | ); | ||
//raise n to the power e, modulo m | |||
function pow(n,e,m){ | |||
if (e<=0) return 1n; | |||
let r = pow(n,e/2n,m); | |||
return (r*r*(e%2n===1n?n:1n))%m; | |||
} | |||
</pre> | |||
</div> | |||
==Prime Billion== | |||
<div class='qu' data-width=300> | |||
Find the first prime bigger than 1 billion | |||
<pre class='usr'> | |||
let b = 1000000000n; | |||
while (b%2n!==0){ | |||
b = b+1n; | |||
} | |||
document.body.innerHTML = `${b}` | |||
//raise n to the power e, modulo m | |||
function pow(n,e,m){ | |||
if (e<=0) return 1n; | |||
let r = pow(n,e/2n,m); | |||
return (r*r*(e%2n===1n?n:1n))%m; | |||
} | |||
</pre> | |||
<pre class='ans'> | |||
let b = 1000000000n; | |||
while (pow(2n,b,b)!==2n){ | |||
b = b+1n; | |||
} | |||
document.body.innerHTML = `${b}` | |||
//raise n to the power e, modulo m | //raise n to the power e, modulo m |
Revision as of 20:58, 26 September 2021
Fermat's little theorem tells us that
xp mod p = x
if p
is prime for x<p
The converse is that if
xp mod p ≠ x
then p is not prime. If the equality holds for some value of x then p is probably a prime. If the equality holds for two values of x then it is even more probable that p is prime. For these questions you can ignore that probability.
Probable primes
Decide which of these numbers is prime:
- 12
- 101
- 4249599619
- 5175703781
- 35563611982942194303
- 82793885002522383103
let pl = [ 12n, 101n, 4249599619n, 5175703781n, 35563611982942194303n, 82793885002522383103n ]; document.body.append(... pl.map(n=>{ let isPrime = n%2n===1n; ret = document.createElement('div'); ret.innerHTML = `${n} is prime: ${isPrime}`; return ret; }) ); //raise n to the power e, modulo m function pow(n,e,m){ if (e<=0) return 1n; let r = pow(n,e/2n,m); return (r*r*(e%2n===1n?n:1n))%m; }
let pl = [ 12n, 101n, 4249599619n, 5175703781n, 35563611982942194303n, 82793885002522383103n ]; document.body.append(... pl.map(n=>{ let isPrime = pow(2n,n,n)===2n; ret = document.createElement('div'); ret.innerHTML = `${n} is prime: ${isPrime}`; return ret; }) ); //raise n to the power e, modulo m function pow(n,e,m){ if (e<=0) return 1n; let r = pow(n,e/2n,m); return (r*r*(e%2n===1n?n:1n))%m; }
Prime Billion
Find the first prime bigger than 1 billion
let b = 1000000000n; while (b%2n!==0){ b = b+1n; } document.body.innerHTML = `${b}` //raise n to the power e, modulo m function pow(n,e,m){ if (e<=0) return 1n; let r = pow(n,e/2n,m); return (r*r*(e%2n===1n?n:1n))%m; }
let b = 1000000000n; while (pow(2n,b,b)!==2n){ b = b+1n; } document.body.innerHTML = `${b}` //raise n to the power e, modulo m function pow(n,e,m){ if (e<=0) return 1n; let r = pow(n,e/2n,m); return (r*r*(e%2n===1n?n:1n))%m; }