Quote:
Originally Posted by Bviper
So here's the third revision of my code. Now, is there anyway I can make it even more efficient? I'm going to try and be calculating very large primes here soon, and don't want any wasted time.
Code:
Code:
public static boolean prime (long IsItPrime)
{
for (int i=1; i<IsItPrime; i+=2)
{
if ((IsItPrime%i==0 && i!=1) || (IsItPrime%2==0 && IsItPrime!=2))
{
return false;
}
}
return true;
}
|
I'd first like to point out a slight error, it starts checking with i = 1. Anything%1 == 0. Start with i = 3.
Now that that's out of the way we can definintely improve the test, but the best methods may be a little above your head. The absolute best way we know to deterministically determine if a number is prime or not is called the
AKS Primality Test and is able to run in polynomial time, but you need to understand number theoretic functions like Euler's totient function.
The next best are the probabilistic primality tests, which can in many cases be faster than AKS, but are unfortunately random. The best of those are simpler to understand, only requiring familiarity with the modulus, the
Miller-Rabian test based on the
Fermat primality test, being most well known. For very large numbers it could be faster to screen them using a few iterations of a probabilistic test, and if they pass, verify with a deterministic method.
If all this is over your head never fear, there are numerous improvements to the type of primality test (called the naive method) you have now that can be easily implemented. First and foremost, IsItPrime is checked with an i that ranges from 1 to IsItPrime - 1. It only needs to be checked up to sqrt(IsItPrime). Why this is true: If IsItPrime is not prime it can be written as x*y where x is prime and y may or may not be prime. Either x and y are the same value (where sqrt(IsItPrime) is x) or one is bigger than the other. if IsItPrime is divisable by the smaller (which is less than sqrt(IsItPrime)) it must be divisible by the larger (which must be bigger than sqrt(IsItPrime)), and we need not check it.
Additionally you can pull the part where you check if IsItPrime%2 == 0 out before the loop, so you don't have to check that every time. You could eliminate it entirely if you made sure the input was not even. If you start with i = 3, you never have to check if i == 1 so that bit can be eliminated too.
, there won't be any above it either
