### grinding_codexp's blog

By grinding_codexp, history, 3 days ago,

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!

 » 3 days ago, # |   +29 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
•  » » 3 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } omg, how i haven't seen this gold from perforator yet, thank u so much haZZlek bro <3
•  » » 2 days ago, # ^ |   +17 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.
•  » » » 44 hours ago, # ^ | ← Rev. 2 →   0 That's cool, I didn't know that. Thanks!
•  » » » 17 hours ago, # ^ |   0 Leaving the code here if anyone needs it.
 » 3 days ago, # |   +4 i think the best way is in $O(\sqrt n)$ which is easy and pretty fast (although not as fast as $O(log(n))$)
•  » » 2 days ago, # ^ |   0 you can also find the "number" of prime numbers before the number "N", in $O(\sqrt n)$
•  » » » 42 hours ago, # ^ |   0 how ?
•  » » » » 22 hours ago, # ^ | ← Rev. 5 →   0 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$)
 » 3 days ago, # |   -8 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)$
 » 3 days ago, # | ← Rev. 2 →   0 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.
•  » » 3 days ago, # ^ |   +10 this test breaks on Carmichael numbers
•  » » » 3 days ago, # ^ |   +10 Thank you for saying this! I learned something new.
 » 3 days ago, # |   0 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.
•  » » 2 days ago, # ^ |   -10 mfs downvoting me for being right
•  » » 2 days ago, # ^ |   0 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."
•  » » » 2 days ago, # ^ |   +3 ight mb
 » 2 days ago, # | ← Rev. 3 →   -21 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=12Numbers 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. int isPrime(num) { if(num ==2|| num==3 ) return num; //Perform open computation here for (var i = 2; i <= temp; i++) { if(num % i ==0) { return false; } } return num; } 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. int isPrime(num) { if(num ==2 || num==3) return num; if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0) return false; //Perform open computation here for (int i = 7; i <= temp; i=i+2) { if(num % i == 0) { return false; } } return num; } 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). int isPrime(num) { if(num == 2 || num == 3 ) return num ; if(num%6 != 1 && num%6 != 5) { return false ; } int tmp = sqrt(num); for(int i = 5; i <= tmp; i+=6 ) if(num % i == 0 || num%(i + 2) == 0) return false; return num; } 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.
•  » » 35 hours ago, # ^ |   +16 are you tripping sir I can see $O(\log n)$ absolutely nowhere in your code
•  » » » 23 hours ago, # ^ |   +3 I guess he is implementing O(sqrt(n)/6) because that one is actually fast ...
•  » » » » 23 hours ago, # ^ |   0 you are correct