2
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ Are you using the sieve of eratosthenes? $\endgroup$
    – Paul
    Commented Apr 2, 2012 at 3:05
  • 3
    $\begingroup$ @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. $\endgroup$
    – Geoff Oxberry
    Commented Apr 2, 2012 at 3:22
  • $\begingroup$ I dont know how to implement it... :/ $\endgroup$
    – Shariff
    Commented Apr 3, 2012 at 3:34
  • $\begingroup$ @Paul : I dont know how to implement it :/ (No I am not using it) $\endgroup$
    – Shariff
    Commented Apr 4, 2012 at 17:02
  • $\begingroup$ @GeoffOxberry: How I delete the question in the math.SE ?? $\endgroup$
    – Shariff
    Commented Apr 4, 2012 at 17:03

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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?? $\endgroup$
    – Shariff
    Commented Apr 3, 2012 at 3:19
  • $\begingroup$ @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. $\endgroup$
    – Pedro
    Commented Apr 3, 2012 at 9:46
  • $\begingroup$ 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... $\endgroup$
    – Shariff
    Commented Apr 4, 2012 at 16:56
  • $\begingroup$ By the way, thanks for your improvements, the runtime was about the half that I have previously $\endgroup$
    – Shariff
    Commented Apr 4, 2012 at 16:57
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi, I know but, How I implement that? I mean I dont know how to translate it into code $\endgroup$
    – Shariff
    Commented Apr 4, 2012 at 16:58
  • $\begingroup$ @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/… $\endgroup$
    – Paul
    Commented Apr 4, 2012 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.