素数判定 高速化
素数判定の高速化に挑戦
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include <stdio.h> #include <math.h> #include <time.h> /* 〜判定の流れ〜 (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 */ int isPrime_new(int n){ // nが1以下ならfalse if(n<=1){ return 0; } // nが2または3ならtrue if(2==n || 3==n){ return 1; } // nが2の倍数ならfalse if(0==n%2){ return 0; } // nの平方根を整数で取得(5なら2, 10なら3) int square_root = (int)sqrt(n); // nがnの平方根以下の、3以上の奇数(3,5,7,9,11,...)で1回でも割れたらfalse for(int i=3; i<=square_root; i+=2){ if(0==n%i){ return 0; } } // 上記すべて回避したらtrue return 1; } /* 高速化前の素数判定アルゴリズム */ int isPrime_old(int n){ if(n<=1){ return 0; } if(2==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 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; } void dispTimeForPrimeSearch_old(int n){ printf("(OLD) "); int cnt = 0; struct timespec tsStart, tsEnd; timespec_get(&tsStart, TIME_UTC); for(int i=-5; i<=n; i++){ if(isPrime_old(i)){ cnt++; } } timespec_get(&tsEnd, TIME_UTC); int nsec = getTimeSpanNanoSec(tsStart, tsEnd); printf("%d以下の素数の数 : %d個\t", n, cnt); printf("所要時間 %f ミリ秒\n", nsec / 1000000.0); } void dispTimeForPrimeSearch_new(int n){ printf("(NEW) "); int cnt = 0; struct timespec tsStart, tsEnd; timespec_get(&tsStart, TIME_UTC); for(int i=-5; i<=n; i++){ if(isPrime_new(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(n); dispTimeForPrimeSearch_old(n); return 0; } |
|
1 2 |
(NEW) 1000000以下の素数の数 : 78498個 所要時間 105.270360 ミリ秒 (OLD) 1000000以下の素数の数 : 78498個 所要時間 224.728172 ミリ秒 |
