tbquan08hanoi's blog

Prime checking
By tbquan08hanoi, history, 6 months ago, In English

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

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

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

miller rabin or fermat there are a lot of famous tests

→ Reply