Difference between revisions of "Testing for prime"

From ProgZoo
Jump to navigation Jump to search
 
(11 intermediate revisions by the same user not shown)
Line 1: Line 1:
<pre id='shellbody' data-qtp='DOM'></pre>
<pre id='shellbody' data-qtp='DOM'></pre>
==Probable primes==
<div class='qu' data-width=300>
Fermat's little theorem tells us that
Fermat's little theorem tells us that
  x<sup>p</sup> mod p = x
  x<sup>p</sup> mod p = x
Line 8: Line 6:
The converse is that if
The converse is that if
  x<sup>p</sup> mod p &ne; x
  x<sup>p</sup> mod p &ne; x
then p is not prime. If the equality holds for some value of x then p is <i>probably</i> 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.
then p is not prime. If the equality holds for some value of x then p is <i>probably</i> 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 assume that if <code>2<sup>p</sup> mod p =2</code> then p is prime.


==Probable primes==
<div class='qu' data-width=300>
Decide which of these numbers is prime:
Decide which of these numbers is prime:
*12
*12
Line 17: Line 17:
*35563611982942194303
*35563611982942194303
*82793885002522383103
*82793885002522383103
*629817083229352620706184583313
*984141389525199908877737938759
<pre class='usr'>
<pre class='usr'>
let pl = [ 12n, 101n, 4249599619n, 5175703781n,
let pl = [ 12n, 101n, 4249599619n, 5175703781n,
  35563611982942194303n, 82793885002522383103n,
  35563611982942194303n, 82793885002522383103n
629817083229352620706184583313n,
984141389525199908877737938759n
];
];
document.body.append(...
document.body.append(...
   pl.map(n=>{
   pl.map(n=>{
     let isPrime = n%2===1;
     let isPrime = n%2n===1n;
     ret = document.createElement('div');
     ret = document.createElement('div');
     ret.innerHTML = `${n} is prime: ${isPrime}`;
     ret.innerHTML = `${n} is prime: ${isPrime}`;
   });
    return ret;
   })
);
);


Line 42: Line 39:
<pre class='ans'>
<pre class='ans'>
let pl = [ 12n, 101n, 4249599619n, 5175703781n,
let pl = [ 12n, 101n, 4249599619n, 5175703781n,
  35563611982942194303n, 82793885002522383103n,
  35563611982942194303n, 82793885002522383103n
629817083229352620706184583313n,
984141389525199908877737938759n
];
];
document.body.append(...
document.body.append(...
   pl.map(n=>{
   pl.map(n=>{
     let isPrime = pow(2,n,n)===2;
     let isPrime = pow(2n,n,n)===2n;
     ret = document.createElement('div');
     ret = document.createElement('div');
     ret.innerHTML = `${n} is prime: ${isPrime}`;
     ret.innerHTML = `${n} is prime: ${isPrime}`;
   });
    return ret;
   })
);
);


Line 59: Line 55:
   let r = pow(n,e/2n,m);
   let r = pow(n,e/2n,m);
   return (r*r*(e%2n===1n?n:1n))%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===0n){
  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
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 Googol==
<div class='qu' data-width=300>
*A googol is 1 followed by 100 zeros.
*Find the first prime bigger than 1 googol
<pre class='usr'>
let b = 1000000000n;
while (b%2n===0n){
  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 = pow(10n,100n);
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);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}
</pre>
</div>
==Primes per Thousand==
<div class='qu' data-width=300>
*For the 1000 numbers from 1000000 to 1000999 how many are prime?
<pre class='usr'>
</pre>
<pre class='ans'>
let b = pow(10n,6n);
let pc = 0;
for(let i=0n;i<1000n;i++){
  let p = b+i;
  if (pow(2n,p,p)===2n)
    pc++;
}
document.body.innerHTML = `${pc}`
//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);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}
</pre>
</div>
==Primes per Thousand Again==
<div class='qu' data-width=300>
*How primes are there in the thousand number starting:
* 1000000 (10<sup>6</sup>),10000000,100000000, ... 1000000000000 (10<sup>12</sup>)
<pre class='usr'>
let ls = [];
for(let j=6n;j<=12n;j++){
  let b = pow(10n,j);
  let pc = 0;
  for(let i=0n;i<1000n;i++){
    let p = b+i;
    if (p%2n!==0n)
      pc++;
  }
  ls.push(`<tr><td>${b}</td><td>${pc}</td></tr>`);
}
document.body.innerHTML = `<table>${ls.join('')}</table>`
//raise n to the power e, modulo m
//m is optional
function pow(n,e,m){
  if (e<=0) return 1n;
  let r = pow(n,e/2n,m);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}
</pre>
<pre class='ans'>
let ls = [];
for(let j=6n;j<=12n;j++){
  let b = pow(10n,j);
  let pc = 0;
  for(let i=0n;i<1000n;i++){
    let p = b+i;
    if (pow(2n,p,p)===2n)
      pc++;
  }
  ls.push(`<tr><td>${b}</td><td>${pc}</td></tr>`);
}
document.body.innerHTML = `<table>${ls.join('')}</table>`
//raise n to the power e, modulo m
//m is optional
function pow(n,e,m){
  if (e<=0) return 1n;
  let r = pow(n,e/2n,m);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}
}
</pre>
</pre>
</div>
</div>

Latest revision as of 09:43, 27 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 assume that if 2p mod p =2 then p is prime.

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===0n){
  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;
}

Prime Googol

  • A googol is 1 followed by 100 zeros.
  • Find the first prime bigger than 1 googol
let b = 1000000000n;
while (b%2n===0n){
  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 = pow(10n,100n);
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);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}

Primes per Thousand

  • For the 1000 numbers from 1000000 to 1000999 how many are prime?

let b = pow(10n,6n);
let pc = 0;
for(let i=0n;i<1000n;i++){
  let p = b+i;
  if (pow(2n,p,p)===2n)
    pc++;
}
document.body.innerHTML = `${pc}`

//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);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}

Primes per Thousand Again

  • How primes are there in the thousand number starting:
  • 1000000 (106),10000000,100000000, ... 1000000000000 (1012)
let ls = [];
for(let j=6n;j<=12n;j++){
  let b = pow(10n,j);
  let pc = 0;
  for(let i=0n;i<1000n;i++){
    let p = b+i;
    if (p%2n!==0n)
      pc++;
  }
  ls.push(`<tr><td>${b}</td><td>${pc}</td></tr>`);
}
document.body.innerHTML = `<table>${ls.join('')}</table>`

//raise n to the power e, modulo m
//m is optional
function pow(n,e,m){
  if (e<=0) return 1n;
  let r = pow(n,e/2n,m);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}
let ls = [];
for(let j=6n;j<=12n;j++){
  let b = pow(10n,j);
  let pc = 0;
  for(let i=0n;i<1000n;i++){
    let p = b+i;
    if (pow(2n,p,p)===2n)
      pc++;
  }
  ls.push(`<tr><td>${b}</td><td>${pc}</td></tr>`);
}
document.body.innerHTML = `<table>${ls.join('')}</table>`

//raise n to the power e, modulo m
//m is optional
function pow(n,e,m){
  if (e<=0) return 1n;
  let r = pow(n,e/2n,m);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}