Definition.
Natural numbers are 0,1,2,... and a natural number x is a factor
of a natural number y iff there is a natural number z with x*z = y.
A natural number p is a prime number iff p > 1 and 1 and p are the only
factors of p.
Theorem.Every natural number other than 0 and 1 has a factor which is
a prime number.
Proof.
Let x ≥ 2 be given. Let y be the smallest factor of x which is
larger than 1; this factor exists as x is a factor of itself; so
x = y * z and 1 < y.
If now y = v * w and 1 < v < y, then v * (w * z) = x and v is a
smaller factor of x than y which does not exist by assumption.
Thus y is a prime number. ▮
How to compute all factors in Java Script?
In Java Scrpit there is an operator "%" which computes the remainder
of a division. So 8 % 3 gives the value 2 and 13 % 4 gives the value 1.
One can use this function to produce a list of factors.
The program which does these computations has one input: the number
x whose factors have to be found. It produces an empty array listvar
and then fills this variable in a loop with the factors of the number
to be factorised.
function factorlist(x)
{ var y; var k = 0;
var listvar = new Array(0);
for (y=1;y<=x;y=y+1)
{ if (x % y == 0)
{ listvar[k] = y; k = k+1; } }
return(listvar); }
One can speed up the process by searching only the factors y which
satisfy y * y ≤ x and then use that also x / y is a factor of x.
This then finds the factors in pairs; at the end it is checked whether
also y, which is at least the square root of x after the loop, is a
factor, that is, equal to the square root. The resulting program
is the following.
function fastfactorlist(x)
{ var y; var k = 0;
var listvar = new Array(0);
for (y=1;y*y<x;y=y+1)
{ if (x % y == 0)
{ listvar[k] = y; listvar[k+1] = x/y; k = k+2; } }
if (y*y == x)
{ listvar[k] = y; k = k+1; }
return(listvar); }
Click below to test the program. Test the above and the below program
with input "10000000" and "68718952447" (the latter is a large prime number).
One can split every number into a list of prime factors which,
when multiplied with each other, give this number. For example,
the prime factorisation of 36 is 2 * 2 * 3 * 3 and the prime
factorisation of 210 is 2 * 3 * 5 * 7. Here prime factors are
repeated in the case that one needs to multiply them several
times to multiply up. Here is a simple programme for this.
The program which is activated by this button is the following.
function primefactorlist(x)
{ var y=2; var k = 0; var z=x;
var listvar = new Array(0);
while (y <= z)
{ if (z % y > 0) { y = y+1; }
else {listvar[k] = y; k = k+1; z = z/y; } }
return(listvar); }
This program can be speeded up, using that the last prime factor is
z in the case that y*y > z. The resulting program is the following.
function fastprimefactorlist(x)
{ var y=2; var k = 0; var z=x;
var listvar = new Array(0);
while (y*y <= z)
{ if (z % y > 0) { y = y+1; }
else {listvar[k] = y; k = k+1; z = z/y; } }
if (z > 1)
{ listvar[k] = z; k = k+1; z = 1; }
return(listvar); }
Click below to test the program. Test the above and the below program
with input "10000000" and "68718952447" (the latter is a large prime number).
The Sieve of Erathostenes.
The Sieve
of Erathosthenes is a method to determine all prime numbers up to a
given bound x. The idea is that to make an array which keeps for each
number y the smallest factor found so far which is not 1. If now
no such factor (except y itself) has been found, one can make sure
that the corresponding factor for all multiples of y is at most y.
This is formalised in the following program.
function smallestfactorlist(x)
{ var listvar = new Array(x+1);
var y; var z;
for (y=0;y<=x;y=y+1)
{ listvar[y] = y; }
for (y=2;y*y<=x;y=y+1)
{ if (listvar[y] == y)
{ for (z=y*y;z<=x;z=z+y)
{ if (listvar[z] > y) { listvar[z] = y; } } } }
return(listvar); }
The first loop initialises all the entries and the second loop then
makes sure that all multiples of those y which are identified to
be primes are then also marked as non-primes so that their smallest
factor is given. It is sufficient to check this for z = y * y, y * y + y,
y * y + 2 * y and so on, as the multiples 2 * y, 3 * y, ..., (y-1) * y
have a smaller factor than y and are already dealt with in previous
runs of the loop. In a second loop one can extract the list of primes
from this variable and store them in a variable "sieve":
var sieve = new Array(0);
var y; var k = 0;
for (y=2;y<=x;y=y+1)
{ if (listvar[y]==y)
{ sieve[k] = y; k = k+1; } }
This can then be displayed on the screen. The following two buttons provide
the list of the smallest factors of the numbers from 0 to x (where 0 is
the smallest factor of 0 and the entry for 1 is 1). The second button produces
the prime numbers until x.
While computations provide large quantities of primes, mathematicians
would of course also be interested whether such a list is finite or
extends beyond any given limit. Already Euclid proved this more than
2300 years ago.
Theorem. The set P of all prime numbers is infinite.
Proof. Assume by way of contradiction that this would not be
the case. Let x be the product of all members of P, so if
P = {2,3,5,7,11} then x = 2 * 3 * 5 * 7 * 11 = 2310. Then x % p is 0
for all p in P. It follows that y = x + 1 satisfies y % p = 1 for
all p in P, for example, 2311 % 11 is 1. Hence y is not a multiple of
any member of P. Furthermore
y > 1 as 2 is in P and x therefore is at least 2. So let z be the
smallest factor of y which is not 1; in the case that y itself is a prime,
z = y (this would be the case in the above example of 2311).
Then z is not in P and z is a prime number.
Thus the set P must be infinite. ▮