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!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | ecnerwala | 3654 |
3 | jiangly | 3627 |
4 | jqdai0815 | 3620 |
5 | orzdevinwang | 3612 |
6 | Benq | 3586 |
7 | Radewoosh | 3582 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3474 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 163 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | atcoder_official | 153 |
5 | maroonrk | 152 |
6 | -is-this-fft- | 148 |
6 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 145 |
10 | cry | 144 |
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!
Название |
---|
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
omg, how i haven't seen this gold from perforator yet, thank u so much haZZlek bro <3
i think the best way is in $$$O(\sqrt n)$$$ which is easy and pretty fast (although not as fast as $$$O(log(n))$$$)
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)$$$
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.
this test breaks on Carmichael numbers
Thank you for saying this! I learned something new.
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.