Miller-Robin
C
views 43
,
size 1901 b
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>

long long power(long long x, unsigned long long y, long long p)
{
long long res = 1;
x = x % p;
while (y > 0)
{
if (y & 1)
res = (res*x) % p;

y = y>>1;
x = (x*x) % p;
}
return res;
}

bool miillerTest(long long d, long long n)
{

long long a = 2 + rand() % (n - 4);

long long x = power(a, d, n);

if (x == 1  || x == n-1)
return true;

while (d != n-1)
{
x = (x * x) % n;
d *= 2;

if (x == 1)      return false;
if (x == n-1)    return true;
}

return false;
}

bool isPrime(long long n, int k)
{
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
long long d = n - 1;
while (d % 2 == 0)
d /= 2;

for (int i = 0; i < k; i++)
if (!miillerTest(d, n))
return false;

return true;
}

int main()
{
int k = 5;

/*printf("input an integer (smaller than 2^32) : ");
int n;
scanf("%ld",&n);
if (isPrime(n,k))
{
printf("probably prime\n");
}else
{
printf("not prime!\n");
}*/
int count = 0;
bool state = true;
for (long long i = 1; i <= 1e8; i++)
{
if (isPrime(i,k))
{
//printf("%4ld ",i);
count++;
//state = true;
}
//if (count%10 == 0 && state)
{
//printf("\n");
//state = false;
}
}
printf("\nthere are %d primes nuder 100000000\n",count);
printf("Method(Miller-Robin test) : Use %d ms\n ",(int)clock());;

return 0;
}