該問題為：
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;
}