Prime numbers are all natural numbers divisible only by 1 and for themselves.

Formula

If I had found a formula to calculate primes I don’t think I would have a blog. More than likely I’d be drinking a Negroni in Fiji.

There is currently no formula that can compute them. On the opposite, it is shown that there is no purely prime number generator polynomial, although there are many polynomials that are able to generate many primes. To understand something like this:

\sum\limits_{i=0}^n a_ix^i=a_nx^n+a_{n-1}x^{n-1}+...+a_0

If we enter the values n=2, a_i=\{41,1,1\} becomes

x_2+x+41

That for 0<=x<=39 is of course a prime number. If you try x=40 magic ends up.

No formula, no function. But even if we can’t generate them on two feet, we can do something.

Primality test

We can see if a number $p is prime. This is trivial. Just divide it by all the numbers from 1 to$p and se what happens. Module % operator is used to calculate the remainder of the division.

But we can optimize the code avoiding unnecessary accounts. It makes no sense to test larger partitions of $p square root because the result of the division would surely be a smaller number than the root of $p . Since the quotient and the divisor are interchangeable in a division, if it were an integer divisor we would have Definitely already tried.

Now you try

Choose 1 < p < 108 and check if it’s prime.

<?php
function isPrime($p, &$i) {
  	for ($i = 2; $i <= sqrt($p); $i++) {
      if (!($p % $i)) return false;
    }
  
	return true;
}


$IN = (array) json_decode(base64_decode($argv[1]));
extract($IN);
$isPrime = isPrime($p, $i);
echo $p.($isPrime ? "" : " non")." è primo\n";
if (!$isPrime) {
 echo "Prova a dividerlo per $i";
}
?>

JSON-formatted Input

{ 
  "p": 7
}
7 is first

The Sieve of Eratosthenes

A quick way to find all the prime factors from 1 to $n could be testing them all via the function we’ve written before. However, the primality test is always performed from 1 to $pfor each $p tested, with an evident repetition of calculations.

Eratosthenes of Cyrene, mathematician of ancient Greece, looked at the problem from another perspective. If we put in a table all the numbers (hence the name sieve meaning sieve) we immediately understand that there is no need to test anything if you change the question from “is $p prime?” to “is $pmultiple?”.

Sieve of Eratosthenes

Our program will not have to do anything other than, starting from 2, eliminate all the multiples until $n of each number it encounters. When it detects an undeleted number, it implies that it is prime.

Credits image: Wikipedia

Prime factors

The prime factors of a number are all divisors of the number that are first.

Here too we could compute them with the primality test on all the numbers from 1 to N (or to its root). We can refine this method by dividing each time by the factor found. In this way we get a smaller number but with the same dividers as the previous one, decreasing the calculation time.

Now you try

Choose 1 < N < 108 and find all of its prime factors

<?php

function primeFactors($N) {
 	$p = []; // $N prime factors. 
    $j = 2; 
    
    while($j <= sqrt($N)) {
        //if it's a divisor
        while(!($N % $j)) {
            //I divide by divisor
            $N /= $j;                 
            $p[$j] = 1;
        }     
        $j++;        
    }
  //Add $N if not 1 because it's a prime divisor (the greatest one)
  if ($N > 1) $p[$N] = 1; 
  return array_keys($p);
}

$IN = (array) json_decode(base64_decode($argv[1]));
extract($IN);
$f = primeFactors($N);

echo implode("\n", $f);

?>

JSON-formatted Input

{ 
  "N": 20
}
2
5

The next step is to find all its divisors.

0 0 votes
Article Rating
Notifiche
Notificami
0 Comments
Inline Feedbacks
View all comments