LeetCode 質(zhì)數(shù)計數(shù)（厄拉多塞篩法）

zhichangterry 發(fā)布于2021-11-15 11:38 / 3044人閱讀

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

問題：

統(tǒng)計所有小于非負整數(shù) n 的質(zhì)數(shù)的數(shù)量。

示例：

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

優(yōu)化做法：
厄拉多塞篩法：
算法詳解及圖片展示

代碼：

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

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

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/123344.html

小李飛刀：做題第八彈！

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

ztyzz 2019-07-31 10:11 評論0 收藏0
LeetCode 204 線性篩 計數(shù)質(zhì)數(shù)

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

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

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

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

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

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

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數(shù)據(jù)結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權之外的使用權限可以從處獲得。 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