判斷一個數是否為素數

来源:https://www.cnblogs.com/shelly-blog/archive/2019/08/29/11431695.html
-Advertisement-
Play Games

一、概念介紹 素數又稱為質數。一個大於1的自然數(從2開始),除了1和它本身外,不能被其他自然數整除的叫做素數,否則稱為合數。 0和1既不是素數也不是合數,最小的素數是2。 二、代碼 方法一: 註意:在for迴圈判斷時不能忘記 i <= sqrt(num) 的等號,因為假設 p*p = n , n的 ...


一、概念介紹

  素數又稱為質數。一個大於1的自然數(從2開始),除了1和它本身外,不能被其他自然數整除的叫做素數,否則稱為合數。

    0和1既不是素數也不是合數,最小的素數是2。

二、代碼

方法一:

bool is_Prime(int num){
    int i;
    
    for(i = 2;i <= sqrt(num);i++){
        if(num % i == 0)//一旦發現有因數,則返回false
            return false;
    }
    return true;
} 

註意:在for迴圈判斷時不能忘記 i <= sqrt(num) 的等號,因為假設 p*p = n , n的因數是可以取到 sqrt(n) 的,如判斷 9 是不是素數,如果沒有等號會出現 9是素數,而實際上 9不是素數。

方法二:

關於質數分佈的規律:大於等於5的質數一定和6的倍數相鄰。例如5和7,11和13,17和19等等;

證明:令x≥1,將大於等於5的自然數表示如下:

··· 6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1 ···

可以看到,不和6的倍數相鄰的數為6x+2,6x+3,6x+4,由於2(3x+1),3(2x+1),2(3x+2),所以它們一定不是素數,再除去6x本身,顯然,素數要出現只可能出現在6x的相鄰兩側。因此在5到sqrt(n)中每6個數只判斷2個,時間複雜度O(sqrt(n)/3)。

在高配版和尊享版中,都是一個剪枝的思想,高配版中裁剪了不必要的偶數,尊享版中裁剪了不和6的倍數相鄰的數,雖然都沒有降低時間複雜度的階數,但都一定程度上加快了判斷的速度。

原文鏈接:https://blog.csdn.net/songyunli1111/article/details/78690447

/*一種高效的方法*/
bool isPrime_3(int num){
    //兩個較小數另外處理
    if(num == 2 || num == 3)
        return true;
    //不在6的倍數兩側的一定不是質數
    if(num % 6 != 1 && num % 6 != 5)
        return false;

    int i;
    //在6的倍數兩側的也可能不是質數 
    for(i = 2;i <= sqrt(num);i += 6){
        if(num % i == 0 || num % (i + 2) == 0)
            return false;
    } 
    
    //排除所有,剩餘的是質數
    return true; 
} 

 

三、測試

  對負數與0,1進行異常處理

 

int main(){
    int num;
    bool result1,result2;
    
    printf("請輸入一個正整數,以-1結束: ");
    scanf("%d",&num);
    while(num < 2 && num != -1){
        printf("輸入不合法,請重新輸入!(說明:素數必須大於1)\n");
        printf("請輸入一個正整數,以-1結束: ");
        scanf("%d",&num);
    } 
    
    while(num >= 2 && num != -1){
        result1 = isPrime(num);
        result2 = isPrime_3(num);
        
        if(result1 == true)
            printf("%d 是素數\n",num);
        else if(result1 == false)
            printf("%d 不是素數\n",num);
    
        if(result2 == true)
            printf("%d 是素數\n\n",num);
        else if(result2 == false)
            printf("%d 不是素數\n\n",num);
        
        printf("請輸入一個正整數,以-1結束: ");
        scanf("%d",&num);
        while(num < 2 && num != -1){
                printf("輸入不合法,請重新輸入!(說明:素數必須大於1)\n");
                printf("請輸入一個正整數,以-1結束: ");
                scanf("%d",&num);
        }
    }
}

 

四、截圖

 


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

-Advertisement-
Play Games
更多相關文章
  • 以下是我經常用到的VScode插件。由於插件本身具有詳細的配置和介紹,不對插件本身的安裝配置進行說明,僅僅支出這些插件的主要功能。具體使用強烈推薦看一下安裝插件後的說明,大多數的問題和設置都可以找到,不要因為是英文就直接上網搜索。 C++類 這兩款插件可以使得C++的編寫變得更加容易。具有強大的自動 ...
  • AttributeError: module 'select' has no attribute 'epoll'   今天烏班圖鏡像莫名其妙損壞了,只好用Windows寫併發TCP伺服器的代碼。運行後,結果發現epoll屬性不存在!!!!我想著在linux下跑的好好的代碼怎麼在W ...
  • 異常處理 什麼是異常處理 (處理異常,報錯error) 捕捉異常 這種方法只能捕捉這個指定錯誤, 當然也有其他錯誤 這樣很麻煩,異常有很多種 這樣就用Exception 就能自動識別錯誤,很方便~ 字元串常用方法 索引取值 切片 成員運算 for迴圈 字元串長度 strip() l.strip() ...
  • 我們看下代碼覆蓋率的統計~,這個不必太揪心,覺得可以幫助你優化代碼,可以看看,也不要帶在意~ 1、先在cmd命令視窗線上安裝coverage 2、安裝完畢後我們在cmd命令視窗輸入:命令 從當前目錄切換到代碼模塊.py文件的所在目錄 3、開始使用coverage統計代碼的覆蓋率,在cmd輸入 all ...
  • 我分了兩種下載安裝的方式給大家看,註意資料庫這個東西不在乎版本是不是最新,在乎的是夠穩定,現在公司中常用的是mysql5.5和mysql5.6的版本,我現在就用mysql5.6的版本給大家來演示一下: 第一種下載安裝的方法: mysql下載地址:https://dev.mysql.com/downl ...
  • 今天的內容主要是,用第三方的HTMLRUNner 第三方的報告來優化之前第五天批量執行案例的測試報告。案例的部分看第五天的批量執行筆記~ HTMLRUNner他可以生成更美觀的測試報告,基於前輩造的車子,我們直接改造使用。先看下運行代碼部分: 首先如果你是python3,你可以直接用我改過的TMLT ...
  • 在 "上一篇文章" 中我們介紹了使用vs2019作為遠程Linux系統的開發環境,但我們是創建的傳統的sln項目,而對於Linux開發者來說以autotools或是cmake進行項目結構的組織更為簡單直觀,也符合在Linux環境上的習慣。 autotools是較為古老的也是使用最為廣泛的構建系統,你 ...
  • 已安裝的環境nginx,python3,mysql,uwsgi,virtualenv 1,創建虛擬環境 2,進入虛擬環境 3,在虛擬環境中安裝flask和uwsgi 4,配置uwsgi,在部署項目的根目錄下創建配置文件uwsgiconfig.ini,添加配置內容如下 5,配置nginx,添加如下內容 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...