ologn_13's blog

Primality Testing
By ologn_13, 12 years ago, In English

Hi all.. I have read about probabilistic primality testing algo's but i want to know about an algo which is deterministic in its approach and which can be coded faster in competition arena(also it should be less confusing in implementation!!) and with best time complexity for larger numbers like 10^20...**please help here** because I got wrong answers most of the time due to long implementation of code and it makes internal steps little bit confusing.. Thanks for reading it..

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

IMHO, Miller-Rabin randomized primality test is very easy to implement, and it's described pretty well in "Introduction to Algorithms". I'd just advise you to read about it carefully.

About deterministic tests: I've read about APR test, which runs in superpolynomial time, but Miller-Rabin test is obviously easier. Also, there exists the AKS test, but though it runs in polynomial time, it's impractical because of the large degree of the polynomial (for an N-bit integer it runs in O(N^6), while Miller-Rabin test runs in O(C * N^3), where C is the number of iterations).

→ Reply
»
12 years ago, # |
  Vote: I like it +26 Vote: I do not like it

BigInteger.isProbablePrime()

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You may want to read about the AKS Primality Test, however, I haven't heard of anyone implementing it in a programming contest.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think miller-rabin is faster than it... but which of them is easier to implement in arena??

    → Reply