Is there any way to find prime number upto 10^9 or 10^18 or more in 1 second?
# | 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 any way to find prime number upto 10^9 or 10^18 or more in 1 second?
Name |
---|
The algorithm:
I have an algorithm which finds the greatest prime less than the given $$$n$$$ and works in less than $$$1$$$ second for $$$n \leq 4\cdot 10^9$$$. I'm not sure if better ones exist.
Let's use a fast prime counting technique. In the mentioned blog, the second one works in $$$O(n^{2/3} \ log^{1/3} \ n)$$$.
We can combine it with binary search on a continuous function. Denote $$$\pi (x)$$$ the number of primes less than $$$x$$$. We know that $$$\pi (\lfloor \frac{x}{2} \rfloor) < \pi (x)$$$, so we set the left and right bound in our binary search to $$$\lfloor \frac{n}{2} \rfloor$$$ and $$$n$$$.
Details of how we do the binary search:
Let's suppose we have some $$$l<r$$$ and $$$\pi (l) < \pi (r)$$$, meaning that there exists a prime on the range $$$(l,r]$$$. Let's take $$$mid = \lfloor \frac{l+r}{2} \rfloor$$$. If $$$\pi (mid) < \pi (r)$$$ it means that there exists a prime on the range $$$(mid,r]$$$, so we set $$$l = mid$$$. Otherwise, $$$\pi (l) < \pi (mid) = \pi (r)$$$ holds, so there exists a prime on the range $$$(l,mid]$$$ and we set $$$r = mid$$$.
We terminate the binary search when $$$r=l+1$$$. Last $$$r$$$ is the greatest prime number less than (or equal to) $$$n$$$.
Complexity:
$$$O(n^{2/3} \ log^{4/3} \ n)$$$, one $$$log\ n $$$ factor comes from the binary search.
Implementation:
The prime gap between two primes is small enough, so to find the greatest prime less than n, you can just iterate through numbers from $$$n - 1$$$ to $$$1$$$ until you'll find the prime (it will occur soon as the prime gap is small). To check if the number is prime you can use primality tests.
In case of $$$n = 10^{18}$$$ this algo will run in approximately $$$1000 \cdot log^2(n)$$$ operations, which is fast enough.