# 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

## 1 Answer

This is just my opinion. I feel this question too broad, and off-topic for math.SE. Stackoverflow and CS.stackexchange would be better venues to discuss methods and algorithms for primality testing, implementation-related issues, including parallelism.

Anyways..

If you're looking for a simple method to find primes up to a certain bound, then you might want to read Sieve of Eratosthenes. In general, there are various methods for primality testing. You can read this wikipedia page. The fastest deterministic algorithms is AKS read here but I doubt it's hard to implement. Miller-Rabin (read here) is a probabilistic algorithm that is not hard to implement.

-
Thanks, but the Sieve of Eratoshthenes means that I have to make a list from 2 to 10,000,000. So that is not what I am searching for. The Miller-Rabin probabilistic algorithm... I just dont get what they are doing... (Taking abstract algebra now...) Anyways, Thanks for the info! –  user28064 Apr 1 '12 at 21:24