Once of the primary advantages of this is that the primorial can be made once and re-used. This means it's a little trickier for small inputs since the included primes can exceed the input, but we could just use a different method for those.
]]>Sorry, I meant to say GCD.
If you multiply all the primes that you have up to the sqrt of n, a single GCD will determine the primality of n. But for the reasons I gave, Java would need a multi-precision library.
]]>E.g. is 57 prime? sqrt(57) is ~7.55 so we need to check all primes through 7. So check 2,3,5,7.
57 % 2 = 1. Continue.
57 % 3 = 0. Found a factor. The number is composite.
Random thoughts:
- remember to include sqrt(n) so we catch perfect squares.
- you can use a test p*p <= n instead of p <= sqrt(n). They each have gotchas in computer implementation: p*p can overflow in most languages, sqrt(n) is not exact in most languages, sqrt(n) is computationally expensive in most languages. The fastest method is to make a variable to store floor(sqrt(n)) before the loop, and make sure you use a good integer square root method. Most of this is moot if you're testing small numbers rather than near the 64-bit boundary.
- ideally we test just the primes, but you can compromise by testing 2 then odds, or 2,3,5 then a +2,+4 wheel (aka a mod-6 wheel), or a mod-30 wheel, etc.
- You can't use a single mod as a deterministic test. You could store lots of primes and do a lookup, which gives an O(1) algorithm making certain assumptions about hashes or O(log n) making other assumptions or using a binary search through a linear table. This doesn't work once the input is larger than your table, and it's terribly memory inefficient. I have seen it done for tiny values (e.g. to 256 or to ~30,000) just because the primes were there. I'm not convinced it is better even if the table exists.
This method is actually one of the fastest for tiny numbers, under a million or so. After that, other methods such as deterministic Miller-Rabin or BPSW are faster. Note that properly implemented for 64-bit inputs, they are *not* probabilistic, but completely correct. For numbers of 20+ digits, the trial division method above is really not practical. We can start using probabilistic and fast methods (e.g. BPSW, which has no known counterexamples), or proof methods.
I'm not sure why AKS got mentioned. If you understand AKS, then trial division should be a trivial concept. AKS is probably not something you want to actually use, as it's quite slow compared to other proof methods. Albeit it is fun to program if you like number theory.
]]>There are probabilistic tests but they are not certain, just very likely to be prime.
]]>is there?
]]>to find our the number prime or not
Your teacher is not the only one that could use a general algorithm.
How large are the numbers he wants it for?
]]>what to do my teacher need an algorithm to find our the number prime or not
I know the AKS text,
but I need to use an method with "if"
like [ if (x%2=0) print " the number is even" ... etc
anyway thanks
]]>for example :
7 , I add +1 to number 7
it will be "8" , when I do that I say after :
8%2=0 if it is true then the number is prime!
and the 7 it prime cause it is true
is that method right? or wrong?
]]>As far as I know, there is no simple way to know.
]]>how to know the number is prime or not buy using % ( mod )?
is there a simple way to know?
]]>