#include <stdio.h>
#include <limits.h>
#include <time.h>
#define NN 10001

int main(int argc,char *argv[]){
	/*----宣言----*/
	unsigned long long int n;	//判定する素数
	int i,j,mode;				//カウンタ,モード
	clock_t start,end;			//経過時間測定用
	int number=0;				//1〜1000までの素数の個数
	bool flag=true;				//フラグ(素数のときtrue、素数でないときfalse)
	bool prime[NN];				//素数か否か判定 
	printf(" ______________________________________\n");
	printf("| 数字の上限は%lldです。|\n",LLONG_MAX);
	printf("| 小数点以下は切り捨てられます。       |\n");
	printf(" --------------------------------------\n");
	
	printf("1:試し割り\n2:エラトステネスの篩\n");
	printf("mode:");
	scanf("%d",&mode);
	printf("素数判定を行う数字(自然数)を入力してください：");
	scanf("%lld",&n);
	//初期化
	for(i=0;i<NN;i++) prime[i] = true;
//計測開始
	start = clock();
	if(n<=1) flag=false;
	else{
	//試し割り
		if(mode==1){
			for(i=2;i<n;i++){
				if(n%i==0) flag=false;
			}
		}
	//エラトステネスの篩
		else{
			for(i=2;i<n+1;i++){
				if(!flag) break;
				for(j=i*2;j<n+1;j=j+i) {
					if(j==n){
						flag=false;
						break;
					}
				}
			}
		}
	}
//計測終了
	end = clock();
	/*----出力----*/
	printf("%dは素数",n);
	if(flag)  printf("です。\n");
	else printf("ではありません。\n");
	printf("%lf[ms]かかりました。\n",(double)(end-start));
	
	/*----素数を数える----*/
	for(i=2;i<NN;i++){
			for(j=i*2;j<NN;j=j+i) prime[j]=false;
	}
	for(i=2;i<NN;i++){
		if(prime[i]==true){
			number++;
			printf("%d ",prime[i]);		
	}
	printf("1〜1000までの素数の個数は%d個です。\n",number);
	return 0;
}