「素数」を編集中 (節単位)

==素数リストの作成==
ある範囲の素数の一覧が欲しい場合、[[エラトステネスの篩]]を使うと効率よく一覧が作れる。
<source lang="c">
#define PRIME_MAX 1000000

int primeNum;
int primeList[PRIME_MAX];
char primeFlag[PRIME_MAX+1];

void makePrimeList(void) {
	int i,j;
	primeNum=0;
	for(i=0;i<=PRIME_MAX;i++)primeFlag[i]=1;
	primeFlag[0]=primeFlag[1]=0;
	for(i=2;i<=PRIME_MAX;i++) {
		if(primeFlag[i]) {
			primeList[primeNum++]=i;
			for(j=i*2;j<=PRIME_MAX;j+=i)primeFlag[j]=0;
		}
	}
}
</source>
このコードは、1からPRIME_MAXまでの素数のリストを求めるプログラムである。<br />
makePrimeList関数を実行すると、primeNumに素数の数が、primeListに素数のリストが格納される。<br />
また、primeFlagにその数が素数かどうかが格納されるので、O(1)で素数判定ができて便利である。