I am using two tests one for numbers<1e13 and miller-rabin test for even larger primes but still my code is unable pass the last test case.Please check what’s wrong with my code:
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector
#define mii map<int,int>
#define pqb priority_queue
#define pqs priority_queue<int,vi,greater >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007 //10^9 + 7
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type*arr = new type[n]
#define w(x) int x;cin>>x;while(x–)
#define ti(n) int n;cin>>n
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);–i)
#define itr(type,it,x) for(type it = x.begin();it!=x.end();it++)
#define endl ‘\n’
#define FIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // to shuffle an array randomly viz. shuffle(arr,arr+n,rng)
typedef tree<int , null_type , less , rb_tree_tag, tree_order_statistics_node_update> PBDS; //policy based data structure
//First check the divisibility by the primes<1e13 => It covers 88% of the primes =>T=sqrt(n)
//But this method can check primes only upto 10^14
//To check even larger primes, refer Miller-Rabin Primality test
const int h = 10000000;
bitset<10000005> b;
vector primes;
void sieve() {
// set all bits
b.set();
b[0] = b[1] = 0;
for (int i = 2; i <= h; i++) {
if (b[i]) {
primes.pb(i);
for (int j = i * i; j <= h; j += i) {
b[j] = 0;
}
}
}
}
bool isPrime(int no) {
if (no <= h) {
return b[no] == 1 ? true : false;
}
for (int i = 0; primes[i]*primes[i] <= no; i++) {
if (no % primes[i] == 0) {
return false;
}
}
return true;
}
//To check primes > 1e14
//It is a probabilistic check, so we have to check for compositeness also.
//For more detais, refer : https://cp-algorithms.com/algebra/primality_tests.html
int power(int x, unsigned int y, int m)
{
int res = 1;
x %= m;
while (y)
{
if (y & 1) res = (res * x) % m;
x = (x * x) % m;
y >>= 1;
}
return res;
}
// This function is called for all k trials. It returns
// false if n is composite and returns false if n is
// probably prime.
// d is an odd number such that d*2r = n-1
// for some r >= 1
//Standard/Best Choice : k == 7 for 64-bit integers and k==3 for 32-bit integers
//T = k*(logn)^3
bool miller_rabin_test(int n, int d)
{
// Pick a random number in [2…n-2]
// Corner cases make sure that n > 4
int a = 2 + rand() % (n - 4);
// Compute a^d % n
int x = power(a, d, n);
if (x == 1 || x == n - 1)
return true;
// Keep squaring x while one of the following doesn't
// happen
// (i) d does not reach n-1
// (ii) (x^2) % n is not 1
// (iii) (x^2) % n is not n-1
while (d != n - 1)
{
x = (x * x) % n;
d *= 2;
if (x == 1) false;
if (x == n - 1) return true;
}
//Return composite
return false;
}
// It returns false if n is composite and returns true if n
// is probably prime. k is an input parameter that determines
// accuracy level. Higher value of k indicates more accuracy.
bool isPrimeLarge(int n, int k)
{
// Corner cases
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Find r such that n = 2^d * r + 1 for some r >= 1
int d = n - 1;
while (d % 2 == 0)
d /= 2;
// Iterate given nber of 'k' times
for (int i = 0; i < k; i++)
if (!miller_rabin_test(n, d))
return false;
return true;
}
int32_t main(int32_t argc, char const *argv[]) {
FIO;
sieve();
w(t)
{
ti(n);
if (n < 1e13)
{
// cout << "Small\n";
if (isPrime(n)) cout << "YES\n";
else cout << "NO\n";
}
else
{
// cout << "Large\n";
if (isPrimeLarge(n, 4)) cout << "YES\n";
else cout << "NO\n";
}
}
return 0;
}