HI! This is primality test and this code is giving only "else condition"(thought it shouldn't) with any number given, but I don't know why... any advices or found mistakes?
//---------------------------------------------------------------------------
#include <iostream>
#include <cmath>
#include <cstdlib>
usingnamespace std;
//---------------------------------------------------------------------------
longlong mod( longlong number, longlong power, longlong n)
{
unsignedlonglong res = 1;
while (power)
{
if (power % 2)
res = (res * number) % n;
number = (number * number) % n;
power /= 2;
}
return res;
}
long GCD(long m, long n)
{
while(m!=0 && n!=0)
{
if(m>=n)
m%=n;
else
n%=m;
}
return m+n;
}
long jacob_char(long a, long b)
{
if (GCD(a, b) != 1)
return 0;
else
{
long r = 1;
if (a < 0)
{
a = -a;
if (b%4 == 3)
r = -r;
}
do
{
long t = 0;
while (a%2 == 0)
{
t += 1;
a /= 2;
}
if (t%2 != 0 && (b%8 == 3 || b%8 == 5))
r = -r;
if (a%4 == 3 && b%4 == 3)
r = -r;
long c = a;
a = b%c;
b = c;
}
while (a != 0);
return r;
}
}
int main(int argc, char* argv[])
{
long n;
long k;
long a;
double t;
int flag = 0;
cin>>n;
cin>>k;
t=1-1/pow(2.0,k);
for (int i=1; i <= k; i++)
{
a=rand()%(n-1)+2;
if (GCD(a, n) > 1)
{
flag=1;
break;
}
elseif (mod(a,(n-1)/2,n) <= jacob_char(a, n))
{
flag=2;
break;
}
}
if (flag != 0)
{
cout<<"composite \n";
}
else
cout<<"prime " << t << "\n";
return 0;
}