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

Quote:

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.

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

- This is an older thread, you may not receive a response, and could be reviving an old thread. Please consider creating a new thread.

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

HappySheep
328 Replies

Ichirou
257 Replies

GRABibus
218 Replies

Recommended Communities