| | 2 3 4 5 6 7 ... (i) | | 2 3 4 5 6 7 ... (n_i) |-------+------------------------------ | 2 2 | 4 6 8 10 12 14 | 3 3 | 6 9 12 15 18 21 | 4 4 | 8 12 16 20 24 28 | 5 5 | 10 15 20 25 30 35 | 6 6 | 12 18 24 30 36 42 | 7 7 | 14 21 28 35 42 49 |... ... |(j)(n_j) (n_ij=n_i*n_j)
エラトステネスの篩は整数列(2,3,4,...,MAX)から、整数同士の積で表せない数(素数)を篩落とすもの。つまり上のn_ij=n_i*n_jで表される数は整数同士の積なので篩の上に残る。後はいかに効率よく篩落とすかの問題。最も実直に行えば。
unsigned int n_to_i(unsigned int n)
{
return n;
}
unsigned int i_to_n(unsigned int i)
{
return i;
}
void bitset(void *bitarray, unsigned int ij)
{
return;
}
void prime_number_print(unsigned int n_max)
{
char *bitarray = (char *)calloc((n_max/CHAR_BIT)+1,sizeof(char));
unsigned int i = 0;
unsigned int j = 0;
unsigned int ij = 0;
unsigned int i_max = n_max;
unsigned int j_max = n_max;
unsigned int n_i = 0;
unsigned int n_j = 0;
unsigned int n_ij = 0;
for(i=2;i<=i_max;i++){
n_i = i_to_n(i);
for(j=2;j<=j_max;j++){
n_j = i_to_n(j);
n_ij = n_i * n_j;
if(n_max <= n_ij){
break;
}
ij = n_to_i(n_ij);
bitset(bitarray,ij);
}
}
return;
}
int main(void)
{
unsigned int n_max = 5;
prime_number_print(n_max);
return 0;
}
だが、これではまだbitset関数とか完成していない。この関数を作る前に考えてみよう。このままだとn_ijは4,6,8,...,25という感じになる。しかし、5より大きい結果についてはn_ijをijに変えても立てるビットが見つからない。