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?


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.


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.

  • $\begingroup$ 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! $\endgroup$ – user28064 Apr 1 '12 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy