Overclock.net banner

1 - 5 of 5 Posts

·
Registered
Joined
·
513 Posts
Discussion Starter #1
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;
}
 

·
Premium Member
Joined
·
5,282 Posts
You should start checking for division at 3, not 1. You should also check for 1 and 2 (as well as other bounds such as negative numbers) before the loop rather than inside of it. Finally, you only need to check up to sqrt(IsItPrime). If there's no divisor less than or equal to sqrt(n), there won't be any above it either
 

·
Premium Member
Joined
·
2,687 Posts
Quote:

Originally Posted by Bviper View Post
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.
 
1 - 5 of 5 Posts
Top