Faster way to find Nth prime

Question

I'm recently trying to go through a list of 100 various exercises in my book, this is currently number 23. Find the Nth prime number, while this seems quite easy, I noticed it takes a long time to search for larger numbers (aka 50000 takes around 47 seconds already.

#include <iostream>
#include <time.h>

using namespace std;
bool checkPrime(int n);

int main()
{   
    while (true)
    {       
        register int number;
        cin >> number;
        register int counter = 0;
        register int numbers = 0;
        time_t start = clock();
        while (counter < number)
        {
            numbers++;
            if (checkPrime(numbers))counter++;
        }
        double time_diff = (clock() - start);
        cout << numbers << endl;
        cout << "Time needed to process in ms: " << time_diff << endl;
    }
}


bool checkPrime(int n) {
    if (n <= 1) return false;
    for (register int i = 2; i < n; i++) {
        if (n%i == 0)return false;
    }
    return true;
}

this is the code itself, nothing too fancy as it's still one of the easier exercises, tried setting the variables as a register as I heard it'd make things faster at times. WolframAlpha needs around 10 seconds to check the 100.000th prime, my code here takes around 90. Thanks in advance, Folling

Answer 1

If you need the nth prime number calculate it very fast. This code fo you Two algorithms used for this

1. First algorithm is Meisel-Lehmer (Meisel-Lehmer very fast calculate count of prime number from 1 to n )
2. Second algorithm is a binary search

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 2;
bool np[N];
int prime[N], pi[N];

int getprime() {
    int cnt = 0;
    np[0] = np[1] = true;
    pi[0] = pi[1] = 0;
    for (int i = 2;i < N;++i) {
        if (!np[i]) prime[++cnt] = i;
        pi[i] = cnt;
        for (int j = 1;j <= cnt && i * prime[j] < N;++j) {
            np[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
    return cnt;
}
const int M = 7;
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;
int phi[PM + 1][M + 1], sz[M + 1];
void init() {
    getprime();
    sz[0] = 1;
    for (int i = 0;i <= PM;++i) phi[i][0] = i;
    for (int i = 1;i <= M;++i) {
        sz[i] = prime[i] * sz[i - 1];
        for (int j = 1;j <= PM;++j) {
            phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
        }
    }
}
int sqrt2(long long x) {
    long long r = (long long)sqrt(x - 0.1);
    while (r * r <= x) ++r;
    return int(r - 1);
}
int sqrt3(long long x) {
    long long r = (long long)cbrt(x - 0.1);
    while (r * r * r <= x) ++r;
    return int(r - 1);
}
long long getphi(long long x, int s) {
    if (s == 0) return x;
    if (s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
    if (x <= prime[s] * prime[s]) return pi[x] - s + 1;
    if (x <= prime[s] * prime[s] * prime[s] && x < N) {
        int s2x = pi[sqrt2(x)];
        long long ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
        for (int i = s + 1;i <= s2x;++i) {
            ans += pi[x / prime[i]];
        }
        return ans;
    }
    return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
long long getpi(long long x) {
    if (x < N) return pi[x];
    long long ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
    for (int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)];i <= ed;++i) {
        ans -= getpi(x / prime[i]) - i + 1;
    }
    return ans;
}
long long lehmer_pi(long long x) {
    if (x < N) return pi[x];
    int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
    int b = (int)lehmer_pi(sqrt2(x));
    int c = (int)lehmer_pi(sqrt3(x));
    ll sum = getphi(x, a) + ll((b + a - 2) * (b - a + 1)) / 2;
    for (int i = a + 1;i <= b;i++) {
        ll w = x / prime[i];
        sum -= lehmer_pi(w);
        if (i > c) continue;
        ll lim = lehmer_pi(sqrt2(w));
        for (int j = i;j <= lim;j++) {
            sum -= lehmer_pi(w / prime[j]) - (j - 1);
        }
    }
    return sum;


}


//32000000000 ---1382799415 count
//25000000000 ---1091987405 count
//23000000000 ---1008309544 count
int main() {
    init();
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    long long n, l, r, res = 0;
    cin >> n;
    l = n;
    if (n == 1)cout << 2;
    else {
        l = 2;
        r = 23000000000;
        while (l < r) {
            ll k = (l + r) / 2, s = lehmer_pi(k);
            if (s >= n) { r = k; }
            else if (s < n) { l = k + 1; }
        }
        cout << r;
    }
}

Answer 2

this is good method for your exercise and for very big numbers

bool chekPrime(unsigned long long int n){
int flag=0;            //flag=0 => flag is not set
if(n<=1||n%2==0)flag=1;//flag=1 => n is not prime
if(n==2||n==3)flag=2;  //flag=2 => n is prime
if(flag==0){
    for(unsigned long long int i=3;i*i<=n;i+=2){
        if(n%i==0){
            flag=1;//flag=1 => n is not prime
            break;
        }
    }
}
//if flag not set or flag=2 => n is prime
if(flag==0||flag==2)return true;
else return false;

}

Answer 3

If you don't have space limitation, create a vector that contains the primes and change your checkPrime method as follows:

vector<int> primes;
bool checkPrime(int n) {
     if (n <= 1) return false;
     for (int i = 0; i < primes.size(), primes.at(i) <= sqrt(n); i++) {

          if (n%primes.at(i)== 0)
               return false;
     }
     primes.push_back(n)
     return true;
}

By this technique, you will only check if n is divisible by a prime instead of all numbers upto its square root.

Here, we leverage that a number is either prime or multiple of one or more primes.

CheckPrime method is O(log n), so finding first N primes is O(n log n) where n is the value of Nth prime

Answer 4

Try this:

#include <iostream>
#include <time.h>
#include <vector>
#include <math.h>

using namespace std;
inline bool checkPrime(int n,std::vector<int>);

int main()
{
    int number,counter,numbers;
    std:cout<<"Prime Searcher";
    std::vector<int> sieve;


    while (true)
    {

        cin >> number;
        counter = 0;
        numbers = 0;
        time_t start = clock();
        while (counter < number)
        {
            if (numbers>2){
                numbers+=2;
            }
            else{
                numbers++;
            }
            if (checkPrime(numbers,sieve)){
                sieve.push_back(numbers);
                counter++;
            }

            }
        double time_diff = (clock() - start);
        cout << numbers << endl;
        cout << "Time needed to process in seconds: " << time_diff/CLOCKS_PER_SEC << endl;
    }
}


inline bool checkPrime(int n, std::vector<int> sieve) {
    double numPrimes=(sqrt(n)/log(sqrt(n))+3);
    if (numPrimes>sieve.size()){numPrimes=sieve.size();}
    if (n <= 1) return false;
    for (int i = 2; i < numPrimes; i++) {
        if (n%sieve[i] == 0)return false;
    }
    return true;
}

By my benchmarking, this is an over 2x optimization for n=4000, and increases with higher numbers. register is depreciated. Any advice about how to further optimize would be appreciated. At n=50000, it takes 24 seconds on my machine.