作者wtchen (沒有存在感的人)
看板C_and_CPP
標題[分享] 精華區2-12，質數搜尋
時間Sat May 23 22:19:14 2015
該問題為：
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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 90.27.173.53
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1432390757.A.C07.html
推 suhorng: sieve j 可從 j*j 開始 05/23 22:33
→ suhorng: 記得篩法也有線性演算法就是 不過要除法 05/23 22:33
推 EdisonX: 還有 step 2j 05/23 22:33
不是說沒想過用 j = i*i
篩法這邊如果是寫這樣
int Prime_Sieve_Eratosthenes(bool *isPrime, int *PrimeNumber) {
int i, j, ans=0;
for (i=2; i<N; ++i){
if (isPrime[i]) {
PrimeNumber[ans++] = i;
for (j=i*i; j<N; j+=i){ -> j = i*i
isPrime[j] = false;
}
}
}
return ans;
}
會造成core dump，看了一下是因為i*i超出範圍(以N=1000000為例，i>1000會爆)
老實說我蠻訝異的，因為j = 2*i會有一樣的問題阿
還有就是math.h 的函式sqrt 或 pow的問題
如果寫a = sqrt(1000000)沒問題
可是double n = 1000000.0; n = sqrt(n)就不行...
(因為N已經宣告在最前面變成全域常數，不想再在函式裡頭重複)
sqrt的使用有那麼麻煩？
※ 編輯: wtchen (90.27.173.53), 05/24/2015 23:05:14
※ 編輯: wtchen (90.27.173.53), 05/24/2015 23:08:00
推 suhorng: 不太對, j = i*i 超出範圍會在 j < N 判掉, 問題是溢位 05/24 23:11
→ wtchen: 可是當i>N/2，j=2*i也是會有同樣情形阿 05/24 23:13
→ suhorng: 超出範圍在 j < N 就判掉了, 不會進迴圈的 05/24 23:22
→ suhorng: 變負數後 j < N 仍然成立才 SIGSEGV 05/24 23:23
→ wtchen: 喔，我懂了，謝謝 05/24 23:28
→ wtchen: 改成long就OK了 05/24 23:32
※ 編輯: wtchen (90.27.173.53), 05/24/2015 23:38:49
→ wtchen: 程式碼也update了，感謝 05/24 23:39
→ wtchen: 至於sqrt的問題是linker error，加了-lm參數就OK了 05/26 01:32