# Easy programmes related to prime numbers

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. ▮