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

Prime checking
Автор tbquan08hanoi, история, 6 месяцев назад, По-английски

Is there a way to check whether an integer is a prime or not in O(log(n))?

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

»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Yes, Test BPSW is non-proved algorithm, that works in O(log3(n)), but at that time there was no counter-case, it was check till 1e15 numbers, so you can use it, but it too difficult, for most of problems O(sqrt(n)) checking is enough. Link to BPSW

→ Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

miller rabin or fermat there are a lot of famous tests

→ Ответить