Hello there. As there is a lot of challanges including prime numbers, i've decided to write a code with a single function, which will check if the number is prime or not, and use it in all the problems. And I have a little problem. My compiler (visual c++) notices nothing wrong in the code, and spoj compilers says, that there is an sigfpe error. I can't find anything wrong, so can't my friends I asked for help. And so i write here.
Idea is to create a single function prime(n) which will return 1 if number is composite and 0 if number is prime. First, i do trial factoring, and after that i try to do Miller-Rabin. I am pretty sure that error is somewhere in function Miller or when I use it. I know there is much work and optimizing to be done, i'm trying to tu just make it work.
Sorry for english, hope comments help. Code:
#include <iostream>
#include <cmath>
using namespace std;
long long int pot(long long int a,long long int b);
long long int pot(long long int a,long long int b,long long int c);
bool Miller(long long int n, int a, int s,long long int d);
bool prime(long long int n);
int main()
{
long long int a;
int t;
cin >> t; //number of test cases
for(int i = 0; i < t; i++)
{
cin >> a; //number to be tested
if(prime(a) == 1)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}
//counts a^b mod c
long long int pot(long long int a,long long int b,long long int c)
{
if(b == 0)
return 1;
if(b % 2 == 1)
return (a * pot(a, b - 1, c)) % c;
else
{
long long int x = pot(a, b/2, c);
return x*x % c;
}
}
//Rabin-Miller prime test
//It tests number n for being prime, the base of powering is a
//and we know that n - 1 = (2^s)*d,
//which was counted before using of this function
bool Miller(long long int n, int a, int s, long long int d)
{
if( pot(a, d, n) == 1)
return 0; //probably prime
else
{
for(int i = 1; i < s; i++)
{
d *= 2;
if(pot(a, d, n) == -1)
return 0; //probably prime
}
}
return 1; //composite
}
bool prime(long long int n)
{
//first- trial factoring. There is much work and optimizing to be done here, so
//please, do not comment about optimizing- i know. ; )
//First- make it work, than make it work well.
//array of small primes for trial factoring
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277,
281, 283, 293};
int k; // k = minimum(sqrt(a), 293). To be changed.
if(sqrt(static_cast<double>(n)) < 293)
k = static_cast<int>(sqrt(static_cast<double>(n)));
else
k = 293;
int i = 0;
while(prime[i] <= k) //trial factoring
{
if(n % prime[i] == 0)
return 1;
else
i++;
}
if(k != 293)
return 0;
int size; //numbers of bases for Rabin Miller test. Probably to be organised in another way.
int tab[7];
long long int h = 4759123141LL;
if( n < h )
{
tab[0] = 2;
tab[1] = 7;
tab[2] = 61;
size = 3;
}
else
{
tab[0] = 2;
tab[1] = 3;
tab[2] = 5;
tab[3] = 7;
tab[4] = 11;
tab[5] = 13;
tab[6] = 17;
size = 7;
}
int s = 0;
long long int d = n - 1; //counting n-1 = (2^s)*d
while(d % 2 == 0)
{
d /= 2;
s++;
}
int p = 0;
int q;
for(p; p < size; p++)
{
q = Miller(n, tab[p], s, d);
if( q == 1)
return 1; //composite
}
return 0;
}
