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