素数判定 isPrime_v180928
当ブログの素数判定の記事が多くの方に読んでいただけているようで嬉しいです。ありがとうございます。
過去記事の素数判定の関数名のnewとかoldとかが整理されておらずすみませんでした。
素数判定関数の最新版(isPrime_v180928)を投稿しますのでこちらを参考にしていただけたら幸いです。
さらなる高速化のため、ロジックを一か所修正しております。
修正前：nが2または3ならtrue
修正後：nが2ならtrueを返す
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
～素数判定 isPrime_v180928の判定の流れ～ 素数の定義：素数とは、1とその数以外の数では割り切れない1以外の正の整数である。 本関数は引数nが素数ならtrueを返す(上から順に判定し、値を返した時点で終了する)。 nが1以下ならfalseを返す。 nが2ならtrueを返す。 nが2の倍数ならfalseを返す。 nの平方根を小数点以下を切り捨てた整数で取得する(5なら2, 10なら3, 15でも3, 16なら4)。 nがnの平方根以下の、3以上の奇数(3,5,7,9,11,...)で1回でも割れたらfalseを返す。 上記すべての判定を回避したらtrueを返す。 (特記事項) 引数に整数の3を渡した場合、 for文の継続判定が一週目から(3<=1)でfalseとなるので、 for文が一週も回らず末尾のreturn 1;が実行される。 これは整数の3は素数なので期待動作となる。 |
|
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 |
#include <stdio.h> #include <math.h> #include <time.h> /* ～素数判定 isPrime_v180928の判定の流れ～ 素数の定義：素数とは、1とその数以外の数では割り切れない1以外の正の整数である。 本関数は引数nが素数ならtrueを返す(上から順に判定し、値を返した時点で終了する)。 nが1以下ならfalseを返す。 nが2ならtrueを返す。 nが2の倍数ならfalseを返す。 nの平方根を小数点以下を切り捨てた整数で取得する(5なら2, 10なら3, 15でも3, 16なら4)。 nがnの平方根以下の、3以上の奇数(3,5,7,9,11,...)で1回でも割れたらfalseを返す。 上記すべての判定を回避したらtrueを返す。 (特記事項) 引数に整数の3を渡した場合、 for文の継続判定が一週目から(3<=1)でfalseとなるので、 for文が一週も回らず末尾のreturn 1;が実行される。 これは整数の3は素数なので期待動作となる。 */ int isPrime_v180928(int n){ // nが1以下ならfalseを返す。 if(n <= 1){ return 0; } // nが2ならtrueを返す。 if(n == 2){ return 1; } // nが2の倍数ならfalseを返す。 if(n % 2 == 0){ return 0; } // nの平方根を小数点以下を切り捨てた整数で取得する(5なら2, 10なら3, 15でも3, 16なら4)。 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 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( 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("isPrime_v180928", isPrime_v180928, n); return 0; } |
|
1 |
(isPrime_v180928) 1000000以下の素数の数 : 78498個 所要時間 86.551737 ミリ秒 |
