Is there a way to check whether an integer is a prime or not in O(log(n))?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Is there a way to check whether an integer is a prime or not in O(log(n))?
Name |
---|
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
miller rabin or fermat there are a lot of famous tests