溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下leetcode中如何實現統計小于非負數n的素數個數，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
leetcode 204.
題目要求：
統計小于非負數n的素數個數。
輸入輸出示例：
Input: 100
Output: 25
解題思路：
題目比較簡單，素數問題也算是各種問題中常見的問題了。首先要明白的一點是，什么是素數？素數又稱為質數，指的是在大于1的自然數中，除了1和它本身外不再有因數的數。
最簡單的思路是，嘗試用n去除2到n-1，發現有整除，可以確認這不是素數。但是這樣很費勁有沒有？要統計個數，就要把所有的數都算一遍。
再考慮一下，n的因數不可能大于sqrt（n），那么遍歷從n到sqrt（n）就夠了。但是這樣還是很慢，如果n不大還行，如果n很大，運力的消耗將很嚴重。
再對素數進行分析，從2到n這中間，仍然會存在很多不靠譜的數字，比如4,6,8等等，他們必然能被2整除，也就是說，凡是2-sqrt（n）的整數倍的數字，那肯定不是素數了。首先把偶數排掉，就去掉了一半的數字，以此類推。
所以，建立一個bool類型的數組，用來標記是素數或者不是素數，長度為n+1.并對它進行初始化，0,1設為false，2,3設為true，從4開始，所有偶數設為false，其他設為true。
然后設置一個i從2到sqrt（n）的循環，仍然跳過偶數。接著內層循環對i的倍數進行標記false，當把sqrt（n）也標記完的時候，整個array就完成了，最后統計一遍true的次數，就可以得到結果了。
不過測試之后發現有個bug，當n很大的時候長度會超出限制，但是我現在想不出更好的方法了，誰能解答一下？歡迎討論。
Java代碼的實現：
public class Solution {
public int countPrimes(int n) {
boolean prime[] = new boolean[n+1];
//initial array 排掉偶數，注意開頭幾個單元的標注
for(int i = 0; i < n+1; i++)
{
if(i == 0 || i == 1)
prime[i] = false;
else if(i < 4)
prime[i] = true;
else if(i % 2 == 0)
prime[i] = false;
else
prime[i] = true;
}
//標記其他單元
for(int i = 3; i < (int)Math.sqrt(n); i += 2)
for(int j = i + i; j < n + 1; j += i)
{
if(prime[j])
{
prime[j] = false;
}
}
int result = 0;
//統計輸出結果
for(int i = 1; i < n+1; i++)
{
if(prime[i])
result++;
}
return result;
}
}
以上是“leetcode中如何實現統計小于非負數n的素數個數”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
