綾小路龍之介の素人思考

エラトステネスの篩

|       |    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に変えても立てるビットが見つからない。

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2007-07-19T23:39:46+09:00
  2. Modified: 2007-07-19T03:55:41+09:00
  3. Generated: 2017-10-16T23:09:17+09:00