# 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?

I also want to mention that I dont want access to a list of numbers because my program does not use the Master-Slave model. I dont have MPI_Send nor MPI_Recv.

I also see something about Miller-Rabin primalirity test, but I dont uderstand it...

Anyway, Ideas??

• Are you using the sieve of eratosthenes?
– Paul
Apr 2 '12 at 3:05
• @Shariff: This is a direct cross-post of the question you posted on math.SE. You have a couple options here. 1) You could delete the question there. 2) You could delete the question here, and flag the question on math.SE (or ask someone to flag it for your) for migration here. If you choose 1), you'll lose the answer you already have; if you choose 2), you'll be able to keep that answer. Apr 2 '12 at 3:22
• I dont know how to implement it... :/ Apr 3 '12 at 3:34
• @Paul : I dont know how to implement it :/ (No I am not using it) Apr 4 '12 at 17:02
• @GeoffOxberry: How I delete the question in the math.SE ?? Apr 4 '12 at 17:03

I'm probably stating the obvious here, but there are several things you could do better... For starters, in your for-loop, you could check if n is even first and then start at i=3 taking steps of 2, e.g. i += 2. This saves you testing against all even numbers.

More elaborately, since you're trying to find all contiguous primes, instead of testing n against all integers < sqrt(n), you would be better off testing it against all primes smaller than sqrt(n).

This is, of course, a bit more difficult to parallelize, but the costs grow with $\mathcal O(n/\log n)$ vs. $\mathcal O(n)$.

However, if you're serious about this, you should probably read-up a bit more on prime numbers to at least understand the Rabin test, as much better methods are available than what you're proposing, even with the improvements I've described.

• hi, thanks for the info of the loop for. the i = 3 sounds good! About testing the sqrt(n), how I test agains the primes smaller than sqrt(n)? I mean, how I can get this primes numbers?? Apr 3 '12 at 3:19
• @Shariff: I assumed you were computing the primes one after the other and storing them somewhere. If you have them in an array, just loop through that array. Apr 3 '12 at 9:46
• I know what r u saying, but, I dont have access to an Array because then I have to do Send and Receive messages, which means that I will have more Overhead (that is not the idea). I think that an implementation on the Sieve of Erasthostenes will be grat, but I dont know how to translate the algorithm in code... Apr 4 '12 at 16:56
• By the way, thanks for your improvements, the runtime was about the half that I have previously Apr 4 '12 at 16:57

The algorithm you implement of course works but it's slow since you need to try lots of long integer divisions: up to sqrt(N) for each number. You will find better algorithms that allow you discard almost all candidate numbers N without having to do these many divisions in any book on prime numbers or algorithmic number theory. I'm sure even wikipedia has suggestions.

Of course, the simplest algorithm you could implement would be the Sieve of Erathostenes, which altogether avoids all divisions.

• Hi, I know but, How I implement that? I mean I dont know how to translate it into code Apr 4 '12 at 16:58
• @Shariff: There is a good explanation of the implementation in Michael Quinn's "Parallel Programing in C with MPI and OpenMP". Here is the code: fac-staff.seattleu.edu/quinnm/web/education/ParallelProgramming/…
– Paul
Apr 4 '12 at 17:05