素数判定 高速化 を関数ポインタでやる
素数判定 高速化
を関数ポインタですっきりさせた
|
1 2 3 4 5 6 7 8 |
〜判定の流れ〜 (nが素数ならtrueを返す) nが1以下ならfalse nが2または3ならtrue nが2の倍数ならfalse nの平方根を整数で取得(5なら2, 10なら3) nがnの平方根以下の、3以上の奇数(3,5,7,9,11,...)で1回でも割れたらfalse 上記すべて回避したらtrue |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <stdio.h> #include <math.h> #include <time.h> int isPrime_old(int n){ if(n<=1){ return 0; } if(2==n || 3==n){ return 1; } int square_root = (int)sqrt(n); for(int i=2; i<=square_root; i++){ if(0==n%i){ return 0; } } return 1; } int isPrime_new(int n){ if(n<=1){ return 0; } if(2==n){ return 1; } if(0==n%2){ return 0; } int square_root = (int)sqrt(n); for(int i=3; i<=square_root; i+=2){ if(0==n%i){ return 0; } } return 1; } int getTimeSpanNanoSec(struct timespec tsStart, struct timespec tsEnd){ int nsec = tsEnd.tv_nsec - tsStart.tv_nsec; int sec = tsEnd.tv_sec - tsStart.tv_sec; if(0 < sec){ nsec += sec * 1000000000; } return nsec; } int dispTimeForPrimeSearch( char* title, int (*primeSearch)(int), int n ){ printf("(%s) ", title); int cnt = 0; struct timespec tsStart, tsEnd; timespec_get(&tsStart, TIME_UTC); for(int i=-5; i<=n; i++){ if(primeSearch(i)){ // landmark cnt++; } } timespec_get(&tsEnd, TIME_UTC); int nsec = getTimeSpanNanoSec(tsStart, tsEnd); printf("%d以下の素数の数 : %d個\t", n, cnt); printf("所要時間 %f ミリ秒\n", nsec / 1000000.0); } int main(){ int n = 1000000; // n以下の素数 dispTimeForPrimeSearch("NEW", isPrime_new, n); dispTimeForPrimeSearch("OLD", isPrime_old, n); return 0; } |
|
1 2 |
(NEW) 1000000以下の素数の数 : 78498個 所要時間 108.884822 ミリ秒 (OLD) 1000000以下の素数の数 : 78498個 所要時間 227.985358 ミリ秒 |
