Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

grinding_codexp's blog

Prime
By grinding_codexp, history, 5 hours ago, In English

Hello codeforces!

I have a question about prime numbers. Is there a way to determine whether an integer is a prime or not in O(log(n)) time complexity?

Thanks!

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

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Google Miller-Rabin test (tho it's not O(log(n))). Also, there is a blog made by peltorator on a simpler method, but unfortunately it is written in russian. https://telegra.ph/Prostoj-test-na-prostotu-09-25

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

    omg, how i haven't seen this gold from perforator yet, thank u so much haZZlek bro <3

    → Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

i think the best way is in $$$O(\sqrt n)$$$ which is easy and pretty fast (although not as fast as $$$O(log(n))$$$)

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You can precompute it for every integer between $$$1$$$ and $$$A$$$ using Sieve of Eratosthenes. I always use normal one that works in $$$O(AlogA)$$$, but there exists a linear one that works in $$$O(A)$$$

If you only want to see for one number $$$n$$$ if it is prime you can do it in $$$O(\sqrt n)$$$

→ Reply
»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There is a probabilistic algorithm. The Fermat's last theorem states that if $$$p$$$ is a prime and $$$a$$$ is a natural number that is not divisible by $$$p$$$, then $$$p$$$ divides $$$a^p - a$$$. It doesn't hold in the opposite direction all the time but most of the time. So if you have some natural number $$$p$$$, just check the condition $$$p$$$ divides $$$a^p - a$$$ for many different a and if all of them hold you are very likely to have a prime number. Time complexity is $$$O(k \log n)$$$ with fast exponentiation where $$$k$$$ is the number of different $$$a$$$ you try. If implemented carefully and correctly you can have an algorithm that is correct practically 100% of the time.

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

    this test breaks on Carmichael numbers

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

      Thank you for saying this! I learned something new.

      → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

The fastest primality test currently is AKS, in 6th power of the logarithm. Essentially making it polynomial in bit size, hence making PRIMES a part of P.

→ Reply