[C言語]:エラトスティンのふるい

1868 ワード
エラトステネスのふるい 白駿 エラトステネス c言語 プログラミング アルゴリズム#アルゴリズム# C テキストリンク
エラトステネスのふるい
  • のアルゴリズムを学ぶには、不可欠な部分がエラトネスのふるいです.ふるいのように数を濾過するので「エラトスティンのふるい」と呼ばれます.
  • ノダ城が立ち並んでいますが、特定の範囲内を判定する少数の人には効率的です.
  • まず1から100までの数字を書きます.
  • 小数を除いても、合成数の唯一の自然数1ではありません.
  • 2以外の2の倍数を除去します.
  • 3以外の3の倍数を除去します.
  • 5の倍数は削除する必要はありません.(2の倍数から削除します.)
  • 2、3を除いて、残りの最小の少数、5の倍数を除去しなければならない.
  • は、最後に7以外の7の倍数を除去する.
    • 例を見てください.
    もし1から300の小数を求めたら、どうしますか.
    <フルコード>
    
#include <stdio.h>
#include <math.h>

#define SIZE 120

int main(void)
{
    int a[SIZE] = { 0 };	// 0 ~ 300
    int i, j;

    for (i = 2; i <= sqrt(SIZE); i++) {	// 최대값의 제곱근까지 반복
        if (a[i] == 0) {		
            for (j = 2; i * j < SIZE; j++) {	// 자신을 제외한 i의 배수 제거
                a[i * j] = 1;
            }
        }
    }

    for (i = 2; i < SIZE; i++) {
        if (a[i] == 0) printf("%d\n", i);
    }

    return 0;
}
  • 11^2>120なので、少量の排水を拭くだけで十分です.すなわち、120以下の数では、2、3、5、7の倍数を除いて、残りの数は少数である.
    • コアコードは2つあります.
    <コード1>
    for (i = 2; i <= sqrt(SIZE); i++) {	// 최대값의 제곱근까지 반복
        if (a[i] == 0) {		
            for (j = 2; i * j < SIZE; j++) {	// 자신을 제외한 i의 배수 제거
                a[i * j] = 1;
            }
        }
    }
    a[i]=0の場合、
  • i=2からずっと回転->
    2(i) x 3(j)
    2(i) x 4(j)
    2(i) x 5(j)
    2(i)x 6(j)等自身以外のiの倍数を除く.(1で示す)
    • <コード2>
        for (i = 2; i < SIZE; i++) {
        if (a[i] == 0) printf("%d\n", i);
    }

    return 0;
}
  • a[i]=0の場合、そのインデックス値が出力されます.
    • Mysql all of the keyword
    名前空間' Google.マップにはエクスポートされていないメンバー' mouseEvent 'がありません