【leetcode】計数質量-エラトストニふるい法

関連資料及び注意事項:

私のLeetCode解題集GitHubアドレス

私信または伝言交流を歓迎します!

アルゴリズムの紹介
自然数n以内のすべての素数を得るには,ルートnより大きくないすべての素数の倍数を取り除かなければならず,残りは素数である.
アルゴリズムプロセス

   for (int i = 0; i < n; i++) {
            arr[i] = true;
        }

        arr[0] = false;
        int count = 0;
        int limit = (int) Math.sqrt(n);
        //         
        for (int i = 2; i <= limit; i++) {
            if (arr[i - 1]) {
                //             
                for (int j = i * i; j < n; j += i) {
                    arr[j - 1] = false;
                }
            }
        }

まず、すべてTrueとしてマークされたブールテーブルarrを確立し、その後、除去を開始する.

は、2からnの開方内の素数を計算するだけでよい.

arrタグが素数である場合、除去が開始される.

jの開始点はi*iであり、i*1 ——> i * (i -1)は以前の(i-1)*iサイクルで除去されたためである.

は、対応する数字が1以上の正の整数であるためarr[j-1]をマークすればよい.同理前判断のa[i-1].

サイクルが完了すると、残りはTrueと表記された素数となる.

心得をまとめる
すばらしいですね.すばらしいですね.