素數篩法(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;
            }
        }
    }

}

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

更多相關文章
  • 本文目錄 一、JPA介紹二、Spring Data JPA類結構圖1、類的結構關係圖三、代碼實現1、添加對應的Starter2、添加連接資料庫的配置3、主要代碼 一、JPA介紹 JPA是Java Persistence API的簡稱,中文名Java持久層API,是JDK 5.0註解或XML描述對象- ...
  • GitHub登錄 分析登錄頁面 開發者工具分析請求 從session請求分析得知: 1.請求的URL為:https://github.com/session 2.該請求為post請求,即需要上傳data表單,所以我們需要分析form-data 由form-data分析得知: 1.login:GitH ...
  • 伺服器數量過多,每次採用ip+埠 輸入密碼的方式登錄比較繁瑣,就採用了免密碼和埠登錄。 普通登錄方式: ssh p 27479 [email protected] 更換免密碼登錄: 本地操作: 本地的公鑰位置: ~/.ssh/id_rsa.pub ~/.ssh目錄下創建一個config文件, ...
  • 廣告檢索服務 功能介紹 媒體方(手機APP打開的展示廣告,走在路上看到的大屏幕廣告等等) 請求數據對象實現 從上圖我們可以看出,在媒體方向我們的廣告檢索系統發起請求的時候,請求中會有很多的請求參數信息,他們分為了三個部分,我們來編碼封裝這幾個參數對象信息以及我們請求本身的信息。Let's code. ...
  • Filter 過濾器 概念:當訪問伺服器的某些資源時,過濾器可以將請求先進行攔截,在完成了一定的特殊功能後,可以讓此請求繼續執行。 一. 實現步驟 1、實現Filter介面 2、重寫方法 3、配置web.xml 二. 過濾器的url配置 完全匹配:攔截指定資源 擴展名匹配: .擴展名,攔截指定尾碼的 ...
一周排行
  • 1. RSA加密與解密 -- 使用公鑰加密、私鑰解密 測試: RSATool myRSA = new RSATool(); Dictionary<string, string> dictK = new Dictionary<string, string>(); dictK = myRSA.GetKe ...
  • 前提 入行已經7,8年了,一直想做一套漂亮點的自定義控制項,於是就有了本系列文章。 GitHub:https://github.com/kwwwvagaa/NetWinformControl 碼雲:https://gitee.com/kwwwvagaa/net_winform_custom_contr ...
  • 1. 在WPF怎麼在UI上添加超級鏈接 這篇文章的目的是介紹怎麼在WPF里創建自定義的HyperlinkButton控制項。很神奇的,WPF居然連HyperlinkButton都沒有,不過它提供了另一種方式用於在UI上添加超級鏈接: 如果需要在超級鏈接里放圖片或其它東西,代碼如下: 這真是很怪,為什麼 ...
  • 系統環境: Windows + .Net Framework 4.0 問題描述: C#連接FTP下載文件時,在部分電腦上有異常報錯,在一部分電腦上是正常的;異常報錯的信息:System.InvalidOperationException: The requested FTP command is n ...
  • 話不多說,上圖: 整體項目結構如圖所示,我的設計初衷是基於.netCore + DI + Vue 打造一個適合初學者的簡捷開發框架。 架構模型採用基於RESTful API風格的前後臺分離框架,總體分為五層:表示層(前端UI)、交互層、業務層、數據訪問層、數據存儲層。 項目中用到的技術如下圖所示: ...
  • 前提 入行已經7,8年了,一直想做一套漂亮點的自定義控制項,於是就有了本系列文章。 GitHub:https://github.com/kwwwvagaa/NetWinformControl 碼雲:https://gitee.com/kwwwvagaa/net_winform_custom_contr ...
  • 初學者經常碰到的,即獲取HTML元素集合,迴圈給元素添加事件。在事件響應函數中(event handler)獲取對應的索引。但每次獲取的都是最後一次迴圈的索引。原因是初學者並未理解JavaScript的閉包特性。 1. <!DOCTYPE HTML> 2. <html> 3. <head> 4. < ...
  • 摘要 本文將介紹如何通過VS2019創建Xamarin.Forms應用程式,以及如何進行調試。 前言 本文介紹Xamarin.Froms應用程式的創建和調試。 開發環境 1.Visual Studio 2019 2.Xamarin.Forms 3.6.0.344457 創建 1.打開VS2019,選 ...
  • 本次應用DevExpress和C#語言製作了一個批量添加水印的程式,看界面效果圖: 界面中既可以進行文字水印添加,也可以圖片水印添加,同時還可以對水印的位置進行設置,比較實用! 文字水印的具體添加情況,看圖: 還可以文字的預覽: 整個文字水印的預覽: 同時圖片的水印預覽: 最後顯示下圖片的水印效果: ...
  • 一、Swagger是什麼 Swagger 是一款RESTFUL介面的、基於YAML、JSON語言的文檔線上自動生成、代碼自動生成的工具。 二、如何在項目中加入Swagger Swagger安裝引用 右鍵Web項目依賴項>管理NuGet程式包>在搜索框輸入"Swashbuckle.AspNetCore ...
x