#include<stdio.h>#include<stdlib.h>#include<math.h>#ifndef MAX_VOLUME#define MAX_VOLUME 500000#endif/*** definite algorithm for prime number test ***/int DefPrime(int n){ int i; for(i = 2; i <= (int)sqrt(n); i++){   if((n % i) == 0)      return 0; } return 1;}/*** get s = pow(a, t) % n, prevent the overflow ***/long long ModularExponent(long long a, long t, long n){ long long s = 1;  while(t > 0){   if((t % 2) == 1)      s = (s * a) % n;   a = (a * a) % n;   t = t / 2;  } return s;}/*** random algorithm for prime number test ***/int Btest(long long a, long n){ long long x; long s, t, i; s = 0, t = n - 1; do{   s++; t = t/2; }while(t % 2 != 1);  x = ModularExponent(a, t, n); if(x == 1 || x == n - 1)   return 1; for(i = 1; i <= s - 1; i++){   x = (x * x) % n;   if(x == n - 1)     return 1; } return 0;}int MillRab(long n){ long long a; a = lrand48() % (n - 3) + 2; return Btest(a, n); }int RepeatMillRab(long n, long k){ long i; srand48((unsigned)time( NULL )); for(i = 1; i <= k; i++)   if(MillRab(n) == 0)     return 0; return 1;}/*** store prime numbers lower than <m> in arrays <primes1> <primes2> got      by algorthms DefPrime and RepeatMillRab respectly ***/int GetPrimes(long m, long primes1[], long primes2[], long *count1, long *count2){ long n, i; primes1[0] = primes2[0] = 2, primes1[1] = primes2[1] = 3; *count1 = *count2 = 2; n = 5, i = 2; do{   if(DefPrime(n)){     primes1[i] = n;     (*count1)++;     i++;   }   n = n + 2; }while(n < m); n =5, i = 2; do{   if(RepeatMillRab(n, (long)log(n))){     primes2[i] = n;     (*count2)++;     i++;   }   n = n + 2; }while(n < m); return 0;}int main(int argc, char **argv){ long primes1[MAX_VOLUME], primes2[MAX_VOLUME]; long count1 = 0, count2 = 0, m, i, j; double prob = 0.0; if(argc != 2){
   printf("Usage: %s <n>          get primes lower than <n>\n", argv[0]);   exit(1);
 } m = atoi(*(argv+1)); GetPrimes(m, primes1, primes2, &count1, &count2);/*不需要此段代碼 for(i = 0; i < count2; i++){   for(j = 0; j < count1; j++){     if(primes1[j] == primes2[i])       break;   }   if(j >= count1)     error++; }*//* for(i= 0; i < count1; i++){   printf("%d ", primes1[i]);   if((i + 1) % 10 == 0)     printf("\n"); }  printf("\n"); for(i= 0; i < count2; i++){   printf("%d ", primes2[i]);   if((i + 1) % 10 == 0)     printf("\n"); }*/  prob = (double)(count2-count1) / count2; printf("m: %d\n", m); printf("count1: %d, count2: %d\n", count1, count2); printf("The error probability: %f\n", prob); return 0;}