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;
}
```

1 - 5 of 5 Posts

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;
}
```

Joined

·
5,282 Posts

Joined

·
2,687 Posts

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.

I as well moved checking for even numbers, 1 and 2 outside the for loop. As well as started at 3.

Runs pretty fast, calculated the first 1,000,000 prime numbers in 7 minutes

1 - 5 of 5 Posts

Join the discussion

Overclock.net

A forum community dedicated to overclocking enthusiasts and testing the limits of computing. Come join the discussion about computing, builds, collections, displays, models, styles, scales, specifications, reviews, accessories, classifieds, and more!

Full Forum Listing
Explore Our Forums

Recommended Communities

Join now to ask and comment!