線性篩法(歐拉篩法)求素數

来源:http://www.cnblogs.com/haizhe/archive/2016/09/25/5906043.html
-Advertisement-
Play Games

時間複雜度O(n)當n比較大時歐拉篩法所用的時間比O(nloglogn)的演算法的時間少的會越來越明顯 為什麼呢? 因為在歐拉篩法中,每一個合數只被訪問並將其所對的f[]的值修改了一次。 ...


時間複雜度O(n)當n比較大時歐拉篩法所用的時間比O(nloglogn)的演算法的時間少的會越來越明顯

為什麼呢?

因為在歐拉篩法中,每一個合數只被訪問並將其所對的f[]的值修改了一次。

for(i = 2; i <= n; i++)
{
    if(f[i] == 0)
    {
        p[++cnt] = i;
    }
    for(j = 1; j <= cnt; j++)
    {
        if(i * p[j] > n)break;
        f[i * p[j]] = 1;
        if(i % p[j] == 0)break;
    }
}

 


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

-Advertisement-
Play Games
更多相關文章
  • 前言 最近要找工作,免不得要有一番筆試,今年好像突然就都流行線上筆試了,真是搞的我一塌糊塗。有的公司呢,不支持Python,Java我也不會,C有些數據結構又有些複雜,所以是時候把STL再看一遍了…不會告訴你距離上次使用可能已經有半年以上了。 STL是什麼 STL為C++的標準模版庫,又稱為C++泛 ...
  • 20160923 定義:將一個類的定義放在另一個類的內部; 從外部類的非靜態方法之外,創建某個內部類的對象:OutClassName.InnerClassName; 內部類擁有所有其外部類的成員的訪問權; 成員內部類不能含有static修飾的變數和方法,因為成員內部類需要先創建了外部類,才能創建它自 ...
  • SpringMVC又一個漂亮的web框架,他與Struts2並駕齊驅,Struts出世早而占據了一定優勢,下麵同樣做一個簡單的應用實例,介紹SpringMVC的基本用法,接下來的博客也將梳理一下Struts2和SpringMVC的一些異同,通過梳理和舊知識的聯繫,讓學習的成本變低,花很短的時間就可以 ...
  • 分別使用序數和enummap的結果: 序數: test1() 使用enummap,tes1t ...
  • 1. Python 文件I/O 本章只講述所有基本的的I/O函數,更多函數請參考Python標準文檔。 2.列印到屏幕 最簡單的輸出方法是用print語句,你可以給它傳遞零個或多個用逗號隔開的表達式。此函數把你傳遞的表達式轉換成一個字元串表達式,並將結果寫到標準輸出如下: 示例1: 運行示例1結果如 ...
  • 【應用場景】:熱門標簽、推薦 【特點】: 在佈局內,隨意擺放任意個view,每行所擺放的view個數,根據實施計算出來的寬度,一旦當前要擺放的view寬度和之前擺放的所有view寬度加在一起,超過了佈局的寬度,那麼就把該view換行擺放。 【佈局】: <LinearLayout xmlns:andr ...
  • maven作為一個項目構建工具,在開發的過程中很受歡迎,可以幫助管理項目中的bao依賴問題,另外它的很多功能都極大的減少了開發的難度,下麵來介紹maven的安裝及與eclipse的集成。 maven的官網地址為:http://maven.apache.org/,打開網頁之後,看到最新的版本是3.3. ...
  • chunkupload簡介 chunkupload是一款基於java語言的斷點續傳組件,針對文件上傳,非文件下載,集成方便,使用簡單。 從整體上講,chunkupload會對文件進行切片處理,每個切片4M大小,預設情況下,chunkupload不會對切片進行合併,筆者也不建議在上傳文件時對切片進行合 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...