prime.c

// 美しい，段下げが実に美しい これならバグがはいりにくですね （ち）
 
#include <stdio.h>
#include <math.h>
 
int main(void)
{
	int i,j,k;
        int sq;                                  // 
	printf("2 ");
 
	for(i=3;i<=100000;i+=2)
	{
		k=0;
//		for(j=3;j<=sqrt(i);j+=2)         // この４箇所の変更で少し速くなります。
                sq = int(sqrt(i));               // なぜだかわかりますか？
                for(j=3; j<=sq; j+=2)            //
		{
			if(i%j==0)
			{
				k=1;
				break;
			}
		}
 
		if(k==0) printf("%d ",i);
	}
 
	printf("\n");
 
	return 0;
 
 
/*
 たとえば，101 が素数であるかを判定するのに 2 から 50 の数字でわって
みなければ，いけないのだろうか？
 11 で割って，われなかったら，素数と判定していいと思う。
 正確には 10 まで，調べれば十分ではないだろうか？
 時間を表示するルーチンをつけておいたから，あちらこちらを変更して
スピードが速くなるようにチューニングして下さい。
 10万までの素数の表をつくると何秒かかるか測ってみてください。
 画面に数字を書くところ（２４行目）は止めてあります。
*/