/********************************/
/* AKS Algorithm */
/********************************/
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <ctime>
#include <cstdlib>
using namespace std;
long GCD(long b,long n); //求最大公因数
bool IsPrime(long r); //判断是否为素数
void main()
{
long n = 0;
_int64 r = 0,q = 0,temp = 1;
int i = 0,j = 0;
cout << "Input an odd number:" ;
cin >> n;
cout << endl;
for(i = 2;i <= n;i++)
{
j = 1;
while(temp = pow(i,j) < n)
j++;
if(temp == n)
{
cout << n << " is a composite!" << endl;
system("pause");
exit(0);
}
}
r = 2;
while(r < n)
{
if(GCD(r,n) != 1)
{
cout << n << " is a composite!" << endl;
system("pause");
exit(0);
}
else if(IsPrime(r))
{
q = r - 1;
if(q >= 4 * sqrt(r) * (log(n) / log(2)) && (long(pow(n,(r - 1) / q)) % r) != 1)
break;
}
r++;
}
for(i = 1;i <= 2 * sqrt(r) * (log(n) / log(2));i++)
for(j = 2;j <= n-1;j++)
{
if(_int64 (pow((j+i),n)) % _int64 (((pow(j,r) - 1))) == (_int64 ((pow(j,n) + i))) % _int64 (((pow(j,r) - 1))))
{
cout << n << " is a composite!" << endl;
system("pause");
exit(0);
}
}
cout << n << " is a prime!" << endl;
system("pause");
}
long GCD(long b,long n)
{
long temp = 0,r = 0;
while((r = n % b) != 0)
{
n = b;
b = r;
}
return b;
}
bool IsPrime(long r)
{
int i = 0;
bool flag = true;
for(i = 2;i <= sqrt(r);i++)
{
if(r % i == 0)
{
flag = false;
break;
}
}
return flag;
}
