#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;
}