I submitted my code in python of WITMATH during the contest and got AC.
When i was submitting the same using C++ it was giving TLE though i had taken all steps to prevent overflow. Please can anyone help. Here’s my code:
/*aayushagarwal*/
#include<cstdio>
#include<cstdlib>
using namespace std;
unsigned long long int mult(unsigned long long int a,unsigned long long int b,unsigned long long int c)
{
unsigned long long int x=0,y=a%c;
while(b>0)
{
if(b%2==1)
{x=x+y;
if(x>c)x=x%c;
}
y=y+y;
if(y>c)y=y%c;
b/=2;
}
return x%c;
}
unsigned long long int modulo( unsigned long long int a, unsigned long long int b, unsigned long long int c)
{
unsigned long long int x = 1;
unsigned long long int y = a;
while (b>0)
{
if (b%2==1)
x = mult(x,y,c);
y = mult(y,y,c);
b = b/2;
}
return x%c;
}
bool millerRabin(unsigned long long int N,unsigned long long int iteration)
{
if (N<2)
return false;
if (N!=2&&N%2==0)
return false;
unsigned long long int d=N-1;
while (d%2==0)
d = d/2;
for (long long int i=0;i<iteration;i++)
{
unsigned long long int a = rand()%(N-1)+1;
unsigned long long int temp = d;
unsigned long long int x = modulo(a,temp,N);
while (temp!=N-1 && x!=1 and x!=N-1){
x = mult(x,x,N);
temp = temp*2;
}
if (x!=N-1 && temp%2==0)
return false;
}
return true;
}
int main()
{
unsigned long long int n;int t;
scanf("%d",&t);
while(t--)
{
bool prime=false;
scanf("%llu",&n);
if(n==2||n==3)
printf("%llu\n",n);
else if(n==4)
printf("3\n");
else if(n==5||n==6)
printf("5\n");
else if(n==7||n==8||n==9||n==10)
printf("7\n");
else if(n==11||n==12)
printf("11\n");
else
{
while(!prime)
{
if(n%2!=0 && n%3!=0 && n%5!=0 && n%7!=0 && n%11!=0)
prime=millerRabin(n,20);
n--;
}
printf("%llu\n",n+1);
}
}
return 0;
}