素数を求めるプログラム

・課題の定番

　100以下の素数を全て表示するプログラムをつくってください。

printf("2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97\n");

・完成までの流れ

　まずは大まかなプログラムの流れを考えてみましょう。

for(i=1;i<=10000;i++)
{
	if(iが素数) printf("%d ",i);
}

iの約数の個数を求める処理

if(iの約数の個数==2) printf("%d ",i);

yakusuu=0;
for(j=1;j<=i;j++)
{
	if(i%j==0) yakusuu++;
}

#include <stdio.h>

int main(void)
{
	int i,j,yakusuu;

	for(i=1;i<=10000;i++)
	{
		yakusuu=0;
		for(j=1;j<=i;j++)
		{
			if(i%j==0) yakusuu++;
		}

		if(yakusuu==2) printf("%d ",i);
	}

	printf("\n");

	return 0;
}

・高速化

　今回のように10000程度ならいいですがもっと大きな素数を求める時は処理を減らし実行速度を上げる工夫が必要になります。 例えば2以外の素数は奇数なので3以降は奇数だけ調べればループ回数は半分ですみます。 また、素数であるかの判定に約数の数を計算するのは無駄です。 iを2からi-1までで割りひとつも割り切れるものがないのが素数という判定法にすれば、ひとつでも割り切れるものがあらわれた時点で途中でチェックをうちきって次の数のチェックに移れるので効率的です。 割る数の範囲はもっとけずれます。 iは奇数に限定しているので割る数は3から奇数のみにできます。 さらにちょっと考えれば分かりますがルートi以上のiの約数はルートi以下のiの約数と対になっているので範囲はルートiまででいいわけです。

#include <stdio.h>
#include <math.h>

int main(void)
{
	int i,j,k;

	printf("2 ");

	for(i=3;i<=10000;i+=2)
	{
		k=0;
		for(j=3;j<=sqrt(i);j+=2)
		{
			if(i%j==0)
			{
				k=1;
				break;
			}
		}

		if(k==0) printf("%d ",i);
	}

	printf("\n");

	return 0;
}