SOHAG_007's blog

How to find the prime number upto 10^9 or more in 1 second?
By SOHAG_007, history, 3 years ago, In English

Is there any way to find prime number upto 10^9 or 10^18 or more in 1 second?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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:

Here
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it

    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.

    → Reply