PrimeNumbers

 It is not difficult to write an algorithm for calculating prime numbers... but what if the number is huge... like 9383362829737? 

I wrote an efficient algorithm  that tells if a number N >=2 is a prime number or not.

On the NET I have found poor algorithm, that works well for lower numbers, but when the number is high, then, they are time consuming. Therefore I decided to publish an efficient algorithm.

The following code use the same amount of time to tell if 3 is a prime number or if 43463847 is a prime number! 


if you found interesting please send an email to: francescopoderico_AT_gmail.com


 The code is written in C and therefore should be quite fast.


#define Natural long int
#define Real double 


int IsPrimeNumber(Natural N){ // N>=2
 Natural s; 
Natural DeltaN; 
Real upper,a,b,k,sum; 
Natural m;

 if( N%2 ==0){
      //printf("\n%d is even",N);
     return 0; 
 } 
 s=0; 
 upper =0;
 a=b=k=sum=0; 
 s = (Natural)floor( (sqrt((Real)N) +1.0)/2.0);
 upper = 1 + (Natural)floor(3.0/(Real)N); sum =0; 
 for(k=1;k<=s;k++){ 
       a = floor((Real)(N)/(2.0*k+1.0));
       b = ((2.0*k+1.0)/(Real)(N)); 
       sum = sum + floor((Real)(b*a));
 } 
 DeltaN = (Natural)floor((upper )/ (1.0+sum)); 
 if (DeltaN == 1){ // N is a prime number 
      printf("\n%d is a prime number",N); 
      return 1;
 } 
 //printf("\n%d is NOT a prime number",N);
 return 0;
 }

Just remember to have an eye on the definition of Natural and Real, you  may need to change type if the number is very high.

Many thanks to prof. S.M.R. Hashemi Moosavi to have found the formula to calculate a prime number.