LeetCode 質數計數（厄拉多塞篩法）

zhichangterry 發布于2021-11-15 11:38 / 2985人閱讀

摘要：問題統計所有小于非負整數的質數的數量。示例輸入輸出解釋小于的質數一共有個它們是。優化做法厄拉多塞篩法算法詳解及圖片展示代碼

問題：

統計所有小于非負整數 n 的質數的數量。

示例：

輸入：n = 10輸出：4解釋：小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。

優化做法：
厄拉多塞篩法：
算法詳解及圖片展示

代碼：

public static int countPrime(int n){        int count = 0;        boolean[] signs = new boolean[n];        for (int i = 0; i < n;i++){            signs[i] = true;        }        for (int i = 2; i < n; i++){            if(signs[i]) {                count++;                for (int j = i + i ; j < n ;j += i){                    signs[j] = false;                }            }        }        return count;    }

云服務器 GPU云服務器篩法求 LeetCode 拉多 LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123344.html

小李飛刀：做題第八彈！

摘要：認真做題的分割線第一題乘積最大子序列難度中等給定一個整數數組，找出一個序列中乘積最大的連續子序列該序列至少包含一個數。寫在前面的話慢慢轉變思路，不再死磕不會做的題，思路可以先借鑒，但是一定要吃透透。上周末看完看完了《算法圖解》，感覺對一些題目的思路有比較大的幫助，但是還是要在實踐中理解。認真做題的分割線第一題 152. 乘積最大子序列難度：中等給定一個整數數組nums，找出一個...

ztyzz 2019-07-31 10:11 評論0 收藏0
LeetCode 204 線性篩計數質數

摘要：存放所有數據，默認全部為素數存放素數，這是有序的，從小到大。如可由或所得，我們只取最小素因子即可假設整數為另一個乘數由如下面我們排除了是一個正整數所以，若能被整除也能被整除 static public int CountPrimes(int n) { //buf 存放所有數據，默認全部為...

不知名網友 2021-11-30 14:52 評論0 收藏0
[LeetCode] Count Primes

摘要：用數組標記非質數，每當出現一個為，計數器加一。關于質數有三點大于的質數一定是奇數，如，，奇數中的非質數也一定是奇數的乘積。首先，我們用從到進行標記。標記完所有的合數之后，再用到之間的遍歷，所有未被標記的質數。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用數組fla...

Shisui 2019-08-14 15:54 評論0 收藏0
Leetcode PHP題解--D57 762. Prime Number of Set Bits

摘要：題目鏈接題目分析對給定范圍內的每個整數，返回其二進制形式下，數字出現的次數為質數的次數。思路由于題目固定了范圍為，次方為千萬。即最多只會出現次。存在則符合題目要求的數字，否則不計入該數字。最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 D57 762. Prime Number of Set Bits in Binary Representation 題目鏈接 762. Prime ...

Cobub 2019-07-01 12:45 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0