1000000以下の素数の数を、配列を使って数える。未整理
|
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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
#include <stdio.h> #include <math.h> #include <time.h> #include <stdlib.h> 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 isPrime_var180928(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; } // lenはn以上ね！ int isPrime_cntPrimeUnderN_var181008_sub(int n, int* a, int cnt) { // nが1以下ならfalseを返す。 if(n <= 1){ return 0; } // nが2または3ならtrueを返す。 if(n == 2){ return 1; } // nが2の倍数ならfalseを返す。 if(n % 2 == 0){ return 0; } int squareRoot = (int)sqrt(n); // nがこれまでに発見した素数で1回でも割れたらfalseを返す。 for(int i = 0; i <= cnt; i ++){ if(0 == n % a[i]){ return 0; } if(squareRoot <= a[i]){ break; } } // 上記すべての判定を回避したらtrueを返す。 return 1; } int cntPrimeUnderN_var181008(int n){ int len = n; int* a = (int*)malloc(len * sizeof(int)); int cnt = 0; for(int i=0; i<=n; i++){ if(isPrime_cntPrimeUnderN_var181008_sub(i, a, cnt)){ a[cnt++] = i; } } free(a); return cnt; } void dispTimeAndCnt_PrimeUnderN(int n){ struct timespec tsStart, tsEnd; timespec_get(&tsStart, TIME_UTC); int cnt = cntPrimeUnderN_var181008(n); timespec_get(&tsEnd, TIME_UTC); int nsec = getTimeSpanNanoSec(tsStart, tsEnd); double msec = nsec / 1000000.0; printf("%d 以下の素数の数 : %d[個], 所要時間 : %f[msec]\n", n, cnt, msec); } int main(){ int n = 1000000; // n以下の素数 dispTimeAndCnt_PrimeUnderN(n); } |
|
1 |
1000000 以下の素数の数 : 78498[個], 所要時間 : 51.212934[msec] |
