Блог пользователя ologn_13

Primality Testing
Автор ologn_13, 12 лет назад, По-английски

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..

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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).

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

BigInteger.isProbablePrime()

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить