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!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | cry | 161 |
2 | awoo | 160 |
2 | maomao90 | 160 |
4 | atcoder_official | 157 |
5 | -is-this-fft- | 155 |
5 | nor | 155 |
7 | adamant | 153 |
8 | maroonrk | 152 |
8 | Um_nik | 152 |
10 | djm03178 | 146 |
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!
Name |
---|
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
But Miller-Rabin test seems can be done in O(log n). For the number in $$$(1,2^{32})$$$, using 3 numbers $$$2,7,61$$$ as the bases can determine whether it's a prime.(This is exactly what ac-library do when they check whether static_modint's mod is a prime or not) And for the number in $$$(1,2^{64})$$$, using 7 numbers $$$2,325,9375,28178,450775,9780504,1795265022$$$ as the bases can determine.
That's cool, I didn't know that. Thanks!
Leaving the code here if anyone needs 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))$$$)
you can also find the "number" of prime numbers before the number "N", in $$$O(\sqrt n)$$$
how ?
sorry i recalculated the order, it was $$$O(n)$$$, but it may be possible, but also $$$O(\sqrt n × \pi(\sqrt n))$$$ can be possible which isn't very different but is a little faster but probably isn't worth it (here $$$\pi(n)$$$ donates then number of prime number before n, and always $$$\pi(\sqrt n) < \sqrt 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.
mfs downvoting me for being right
https://en.wikipedia.org/wiki/AKS_primality_test "While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a galactic algorithm. For 64-bit inputs, the Baillie–PSW test is deterministic and runs many orders of magnitude faster. For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is far superior to AKS."
ight mb
Method 1:O(logN) The above judgment method clearly has the problem of extremely low efficiency. For each number n, it is not necessary to judge from 2 to n-1. We know that if a number can be factorized, the two numbers obtained during factorization must be one less than or equal to sqrt (n) and one greater than or equal to sqrt (n). Based on this, the above code does not need to traverse to n-1, it only needs to traverse to sqrt (n), because if the divisor cannot be found on the left side of sqrt (n), then the divisor 12 cannot be found on the right side either.
1×12=12 2×6=12 3×4=12 4×3=12
Numbers that can be divided by 2 are definitely not prime numbers, so they do not need to be divided by 4 or 6, which can reduce the number of n/2 executions. Numbers that can be divided by 3 are definitely not prime numbers, so they do not need to be divided by 6 or 9, which can further reduce the number of executions.
Method 2:O(logN/2) 2x, 3x, 5x are definitely not prime numbers.
At this point, it is possible to fast forward 2 prime numbers as a unit, that is, in the loop, the i++step size is increased to 2, which speeds up the judgment process.
Method 3:O(logN/6) Proof: Let x ≥ 1, and express the natural numbers greater than or equal to 5 as follows:
······ 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ······
As can be seen, the numbers outside the sides of multiples of 6 are 6x+2, 6x+3, and 6x+4. Since 2 (3x+1), 3 (2x+1), and 2 (3x+2) are not prime numbers, and 6x itself is not prime. So on both sides of multiples of 6 must be prime numbers, and: if (num% 6!=1&&num% 6!=5) return false; Adjacent sides of multiples of 6 are not necessarily prime numbers. At this point, it is possible to fast forward 6 prime numbers as units, which means that in the loop, the i++step size is increased to 6, speeding up the judgment process. The reason is that if the number to be determined is n, then n must be in the form of 6x-1 or 6x+1. For loops 6i-1, 6i, 6i+1, 6i+2, 6i+3, and 6i+4, if n can be divided by 6i, 6i+2, and 6i+4, then n must be at least an even number. However, the form of 6x-1 or 6x+1 is clearly an odd number, so it does not hold. In addition, if n can be divided by 6i+3, then n can be divided by 3 at least, but 6x can be divided by 3, so 6x-1 or 6x+1 (i.e. n) cannot be divided by 3, so it does not hold. In summary, only the cases of 6i-1 and 6i+1 need to be considered in the loop, that is, the step size of the loop can be set to 6, and each time the loop variables k and k+2 are judged, the overall speed should theoretically be three times that of method (2).
I hope my advice can help you. If there are some mistakes, please point them out and I am very happy to correct them. Thanks for your reading.
are you tripping sir I can see $$$O(\log n)$$$ absolutely nowhere in your code
I guess he is implementing O(sqrt(n)/6) because that one is actually fast ...
you are correct
You can check out this blog that i found interesting blog