C言語関係掲示板

過去ログ

No.５１８．3からｎの間にある奇数の数

[戻る]　[ホームページ]
No.4052
数学に関するプログラム
投稿者---匿名希望(2002/12/25 16:02:59)


ある素数を計算するためのプログラムについて分析しています。
そのソースの中でで分からないことがいくつかあるので、
ここで取り上げようと思います。お願いします。

TheNumberOfKisu = (n-1) / 2;
こうするとなぜ3からｎの間にある奇数の数が求まるのでしょうか？
実際実数を入れて試して考えたのですが、やっぱり分かりませんでした。

char *array;
int i, j;
for ( i = 3; i < n/3; i += 2 ) {
        if ( array[i/2-1] ) {
            for ( j = i*2; j <= n; j += i )
                if ( j&1 )
                    array[j/2-1] = 0;
        }
}
この部分でi の倍数(i 自身は除く)を弾いていく（状態を0にする）作業をしているのだそうですが、特にif ( j&1 )のところがよく分かりません。

お願いします。
No.4062
Re:数学に関するプログラム
投稿者---eripong(2002/12/26 00:25:00)


とりあえず最初の質問についてだけです。
cがどうのというより数学の問題っすね｡

1.nが3以上の偶数だとすると､
  n == 2 * (m + 1)
  となる自然数mが存在します｡ 
  こういうmを考えると､
  (n-1) / 2
  ==(2 * m + 2 - 1) / 2
  ==(2 * m + 1) / 2
  となり、mがintの場合は
  1/2が切り捨てられて
  結果はmになります｡
  つまり(n - 1) / 2 == m
  さて、nが偶数であるときn以下の整数は偶数と奇数が
  同じ個数だけ存在します｡
  したがって、n以下の奇数はm+1個存在しますが､
  そのうちの一つは1なので、3以上n以下の奇数は
  m個になります｡

2.nが３以上の奇数だとすると､
  n == 2 * m + 1
  となる自然数mが存在します｡
  すると、
  (n - 1) / 2 == (2 * m - 1) / 2 == m
  となります。
  nは奇数なので､n以下の奇数の個数は偶数の個数より一つ
  多く､つまりはそれぞれm+1個､m個ずつあることになります｡
  1.の場合と同様に､この個数には1が数えられているので､
  3以上n以下の奇数はm個あることになります｡


てな感じでどうでしょう?