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?