该问题为：
1 不是质数，请问：从 1 to 1,000,000一共有几个质数？
使用 什么方法最快？你的计算时间是多少？精确度要 小于 0.1秒。
试着用循序搜寻法(Sequential Search)跟筛法(Sieve of Eratosthenes)
然后用sys/time.h的timer定时(因为精度需要小于0.1s)
再稍微调整了一下coding，尽可能不重复同样的coding...
(第一次用函数指标)
这次完全用c的语法写...
(本来是用vector，但是发现用malloc+pointer速度稍微快一点)
原始码同步分享在这
https://gist.github.com/gnitnaw/9db341d4588ff5431c45
希望各位先进能指教。
PS: 输出结果：
1. Sequential Search :
Number of Primes : 78498
Total time : 14708.000000 ms
2. Sieve of Eratosthenes :
Number of Primes : 78498
Total time : 16.000000 ms
//====================================================================//
#include <sys/time.h> // timer
#include <stdio.h> // printf
#include <stdlib.h> // malloc, free
#include <stdbool.h> // bool
const int N = 1000000; // Range of Prime
const int nTest = 2; // Two test
struct Measurement {
int nPrime; // number of Primes
double time_use; // Duration
};
int Prime_Sequential_Search(bool *isPrime, int *PrimeNumber);
// Return the number of Primes
int Prime_Sieve_Eratosthenes(bool *isPrime, int *PrimeNumber);
// Return the number of Primes
struct Measurement Time_Measure(bool *isPrime, int *PrimeNumber,
struct timeval *start_time, struct timeval *end_time,
int (*prime)(bool*, int*));
// 测量该方法跑完所需时间
void reset(bool *isPrime, int *PrimeNumber);
int main(){
struct timeval start_time, end_time;
bool *isPrime = malloc(N * sizeof(bool));
int *PrimeNumber = calloc(N/2, sizeof(int));
struct Measurement *measure = malloc(nTest * sizeof(struct Measurement));
printf("1. Sequential Search : \n");
measure[0] = Time_Measure(isPrime, PrimeNumber, &start_time, &end_time,
Prime_Sequential_Search);
printf("2. Sieve of Eratosthenes : \n");
measure[1] = Time_Measure(isPrime, PrimeNumber, &start_time, &end_time,
Prime_Sieve_Eratosthenes);
free(isPrime) ;
free(PrimeNumber) ;
free(measure);
return 0;
}
int Prime_Sequential_Search(bool *isPrime, int *PrimeNumber) {
int i, j, ans=0;
for (i=2; i<N; ++i) {
if (ans == 0) {
PrimeNumber[ans++] = i;
} else {
for (j=0; j<ans; ++j) {
if (i%PrimeNumber[j] == 0) {
isPrime[i] = false;
break;
}
}
if (isPrime[i]) {
PrimeNumber[ans++] = i;
}
}
}
return ans;
}
int Prime_Sieve_Eratosthenes(bool *isPrime, int *PrimeNumber) {
long i, j, ans=0;
for (i=2; i<N; ++i){
if (isPrime[i]) {
PrimeNumber[ans++] = i;
for (j=i*i; j<N; j+=i){
isPrime[j] = false;
}
}
}
return ans;
}
struct Measurement Time_Measure(bool *isPrime, int *PrimeNumber,
struct timeval *start_time, struct timeval *end_time,
int (*prime)(bool*, int*)) {
reset(isPrime, PrimeNumber);
struct Measurement ans;
gettimeofday(start_time,0);
ans.nPrime = prime(isPrime, PrimeNumber);
gettimeofday(end_time,0);
ans.time_use = 1000*(end_time->tv_sec - start_time->tv_sec) +
(end_time->tv_usec - start_time->tv_usec)/1000;
printf("Number of Primes : %d\n", ans.nPrime);
printf("Total time : %f ms\n\n", ans.time_use);
return ans;
}
void reset(bool *isPrime, int *PrimeNumber) {
for (int i=0; i<N; ++i){
if (i<N/2) PrimeNumber[i] = 0;
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
}