#include #include #include #include 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; }