素數篩法(Eratosthenes篩法)

来源:https://www.cnblogs.com/KeepZ/archive/2019/08/12/11343202.html

介紹 Eratosthenes篩法,又名埃氏篩法,對於求1~n區間內的素數,時間複雜度為n log n,對於10^6^ 以內的數比較合適,再超出此範圍的就不建議用該方法了。 篩法的思想特別簡單: 對於不超過n的每個非負整數p, 刪除2p, 3p, 4p,…, 當處理完所有數之後, 還沒有被刪除的就是 ...


介紹

Eratosthenes篩法,又名埃氏篩法,對於求1~n區間內的素數,時間複雜度為n log n,對於10^6^ 以內的數比較合適,再超出此範圍的就不建議用該方法了。
篩法的思想特別簡單: 對於不超過n的每個非負整數p, 刪除2p, 3p, 4p,…, 當處理完所有數之後, 還沒有被刪除的就是素數。

代碼

void init()
{
    int cnt=0;
    for(int i=0;i <= Max;i++)
        is_prime[i] = true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=Max;i++)
        if(is_prime[i])
        {
            prime[cnt++]=i;     //邊篩邊記錄素數
            for(int j=2*i;j<=Max;j+=i)
                is_prime[j]=false;
        }
}

對應題目:Prime Gap UVA - 1644
對應題目代碼:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
const int maxn = 100001, Max = 1299721;
int prime[maxn];
bool is_prime[Max+1];
void init()
{
    int cnt=0;
    for(int i=0;i <= Max;i++)
        is_prime[i] = true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=Max;i++)
        if(is_prime[i])
        {
            prime[cnt++]=i;     //邊篩邊記錄素數
            for(int j=2*i;j<=Max;j+=i)
                is_prime[j]=false;
        }
}
int main()
{
    std::ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    init();
    while(cin >> n && n)
    {
        if(is_prime[n])     
        {
            cout << 0 << endl;
            continue;
        }
        for(LL i = 0; i < maxn; i++)
        {
            if(prime[i] > n)
            {
                if(prime[i] != n)
                    cout <<  prime[i] - prime[i-1] << endl;
                break;
            }
        }
    }

}

您的分享是我們最大的動力!

更多相關文章
  • Windows下Beyond Compare 4 30天評估到期了的話,可以嘗試下麵兩種方式: 破解方式把Beyond Compare 4安裝文件夾下麵的BCUnrar.dll文件刪掉就行了,但是這種依然會提示在試用期 BC4註冊碼:可以用下麵這個註冊碼,有效期是到2019年12月 BEGIN LI ...
  • 使用dir()我們可以知道這個數據類型的內置函數有什麼方法: 1.迭代器 iterable:可迭代的 迭代就是將數據能夠一個一個按順序取出來 上面數據類型返回為真說明它是可以迭代的,反之是不可迭代的 可迭代協議: 就是內部要有一個__iter__()來滿足要求 當一個具有可迭代的數據執行__iter ...
  • 通過DefaultMQPullConsumer作為預設實現,這裡的啟動過程和Producer很相似,但相比複雜一些 【RocketMQ中Producer的啟動源碼分析】 DefaultMQPullConsumer的構造方法: 這裡會封裝一個DefaultMQPullConsumerImpl,類似於P ...
  • 1.爬取豆瓣top250書籍 結果 2.把評分為9.0的書籍保存到book_out.csv文件中 ...
  • 零基礎學python,python視頻教程 這是我收集到的互聯網上的視頻資源,所有內容均來自互聯網。僅供學習使用。 目前我在也在學習過程中,會把學習過程中遇到問題以及解決問題的方式,總結到我的公眾號【趣學程式】裡面。 偶爾會發表幾篇文章,供給大家學習使用。茫茫人海之中,只為交個朋友。還請多多多指教小 ...
  • 最近整理ssm,寫完demo案例,無論如何都訪問不了後臺,百度了好多,終於解決了問題所在 先看頁面信息: 因為一直報404錯誤,一直找路徑是不是弄錯了,或配置文件弄錯了,僅僅這個配置文件都看了無數遍,然而並沒有發現問題,後來百度這個描述才發現了問題The origin server did not ...
  • 這是一篇修改class文件的文章。註釋並不完全,要抓住這次練習的目的: boolean在虛擬機中是以何種方式解讀的 好的,開始我的表演 1.安裝asmtools.jar(本文尾部有步驟) 2.編寫一個java文件,並編譯,執行 2.1 Foo.java 1 public class Foo { 2 ...
  • 本文將通過for ... in ...的語法結構,遍歷字元串、列表、元組、字典等數據結構。 字元串遍歷 列表遍歷 元組遍歷 字典遍歷 1. 遍歷字典的key(鍵) 2. 遍歷字典的value(值) 3. 遍歷字典的項(元素) 重點:帶下標索引的遍歷 正常情況我們是這樣的 升級版使用 enumerat ...
一周排行
  • 前言 上一篇文章介紹IOptions的註冊,本章我們繼續往下看 IOptions IOptions是一個介面裡面只有一個Values屬性,該介面通過OptionsManager實現 OptionsManager OptionsManager實現了IOptions和IOptionsSnapshot,他 ...
  • 在 EF 里有個 `ShadowProperty` (陰影屬性/影子屬性)的概念,你可以通過 FluentAPI 的方式來定義一個不在 .NET model 里定義的屬性,只能通過 EF 里的 `Change Tracker` 來操作這種屬性。 在導出 Excel 的時候,可能希望導出的列並不... ...
  • 使用NPOI操作Excel,無需Office COM組件 部分代碼來自於:https://docs.microsoft.com/zh-tw/previous-versions/ee818993(v=msdn.10)?redirectedfrom=MSDN using System.Data; usi ...
  • Spire.Cloud.Word.Sdk提供了介面SetBackgroudColor()、SetBackgroudImage()、DeleteBackground()、GetBackgroudColor()用於設置、刪除及讀取Word文檔背景。本文將以C#程式為例演示如何來調用API介面實現以上內容 ...
  • 說明:在同一視窗打開鏈接,只要稍加改造就可以實現,這裡實現的是在新Tab頁打開鏈接,並且支持帶type="POST" target="_blank"的鏈接 github和bitbucket上相關問題: 1、WPF empty POST data when using custom popup htt ...
  • 前言 公司項目需要做個畫線縮放,我司稱之為瞳距縮放,簡而言之就是:2張圖,從第一張圖畫一條線,再從第二個圖畫一條線,第二條線以第一條為基準,延長到一致的長度,並同比縮放圖片;文字太枯燥,請先實例圖 例子1:以皮卡丘為例,我要把路飛的拳頭縮放到皮卡丘頭那麼大 例子2:以皮卡丘的基準,縮小路飛,與其身高 ...
  • 9月份的時候,微軟宣佈正式發佈C 8.0,作為.NET Core 3.0發行版的一部分。C 8.0的新特性之一就是預設介面實現。在本文中,我們將一起來聊聊預設介面實現。 作者:依樂祝 原文鏈接:https://www.cnblogs.com/yilezhu/p/12034584.html 提前說下: ...
  • 對於地圖坐標偏移,以leaflet為例,有如下解決辦法 方法1、修改leaflet源碼,解決地圖坐標偏移問題 方法2、將點位真實的經緯度經過偏移演算法,添加到加密的地圖上 方法3、直接對離線地圖瓦片進行糾偏 方法1需要修改源碼 方法2有缺陷,地圖依然是偏移的,如果把地圖經緯度顯示出來,經緯度也是不對的 ...
  • 引用類庫 1.Install-Package Microsoft.Extensions.Caching.Memory MemoryCacheOptions 緩存配置 1.ExpirationScanFrequency 獲取或設置對過期項的連續掃描之間的最短時間間隔 2.SizeLimit 緩存是沒有 ...
  • 原文:https://blogs.msdn.microsoft.com/mazhou/2017/12/12/c-7-series-part-7-ref-returns/ 背景 有兩種方法可以將一個值傳遞給一個方法: 例如,FCL(.NET Framework Class Library)中的Arra ...
x