Miller-Robin
raw download clone
C
views 26
,
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; 
}
close fullscreen
Login or Register to edit or fork this paste. It's free.