# Contiguous prime numbers with MPI (Want more ideas for an efficient algorithm)

I am a programmer. I am working with Message Passing Interface (MPI) in C. I do a program that consist on finding the contiguous prime from 1 to 10,000,000.

I already do it! but I do it with trial division, testing the square root of the number to see if it is prime.

For example, to check for a number n, if it is prime:

int Isprime(int n){

for(i = 2; i <= ceil(sqrt(n)); i++)
{
if(n%i == 0)
return 0;
}

return 1; }


Meaning that if a number i which is less than or equal to the square root of a specified number, and i divides it, then the specified number is not prime.

Does someone know something more accurate? I mean more efficient to do this? Is there a more efficient algorithm to determine if a number is prime? Is there some important property of primes that I overlooked?

The run time of my program is good, but I want more! :) Ideas?

-
Miller-Rabin Primality Test –  pedja Apr 1 '12 at 5:24
Prime Sieve of Eratosthenes –  pedja Apr 1 '12 at 5:30
scicomp.SE would also gladly take your question; we take lots of questions on MPI, and on the practical implementation of parallel algorithms. (I'm a mod on scicomp.SE.) –  Geoff Oxberry Apr 1 '12 at 6:04
hi Geoff Oxberry, Can you help me? –  user28064 Apr 1 '12 at 20:40
Math.SE mods: Cross post on scicomp.SE. –  Geoff Oxberry Apr 4 '12 at 16:25