一文解決如何使用 C 語言判斷質數(素數)[ 附解析與源碼 ]

来源:https://www.cnblogs.com/main-studio/archive/2023/01/21/17064035.html
-Advertisement-
Play Games

前言 質數歷來都是數學界的寵兒,是數學里神秘的謎團。 質數又和 C 語言有著不解之緣,本篇文章將講解如何用 C 語言判斷質數。 為了方便大家在讀完此文章後使用文中程式,我會將判斷質數的程式封裝成函數,此函數的功能是:判斷形參 _number 是否是質數,若 _number 是質數,則返回 1;若不是 ...


前言

質數歷來都是數學界的寵兒,是數學里神秘的謎團。

質數又和 C 語言有著不解之緣,本篇文章將講解如何用 C 語言判斷質數。

為了方便大家在讀完此文章後使用文中程式,我會將判斷質數的程式封裝成函數,此函數的功能是:判斷形參 _number 是否是質數,若 _number 是質數,則返回 1;若不是質數,則返回 0

何為質數

質數又稱素數。一個大於 1 的自然數,除了 1 和它自身外,不能被其他自然數整除的數叫做質數;否則稱為合數(規定 1 既不是質數也不是合數)。

C 語言判斷質數

在瞭解了質數的定義後,現在我們便可以著手編寫程式啦。

現在給定一個正整數 number,要求我們判斷此數是否為質數。針對這一要求本篇採用兩種判斷方法,分別是:暴力求解 與 巧用平方根。

暴力求解

通過質數的定義可以得到如何判斷一個數是否為質數, 我們可以通過遍歷從 2number - 1 這個區間中的所有數,如果都不能被 number 整除,則 number 是質數,否則 number 不是質數。

具體代碼如下:

/****************************************************************************
* 函數名:  Judge_PrimeNumber
* 功能描述:判斷一個數是否為質數
* 輸入參數:
*			_number:需要判斷的數
* 返回值:
*			1:是質數
*			0:不是質數
* 外部參數:無
* 註意事項:無
*
* 作者:	梁國慶
* 日期:	2021-12-11
* 修改記錄:
****************************************************************************/
int Judge_PrimeNumber(int _number)
{
    int i = 0;

    if (_number < 2)
    {
        return 0;   /* 需要判斷的數小於 2,則不是質數,返回 0 */
    }

    for (i = 2; i < _number; i++)   /* 遍歷從 2 到 _number - 1 區間中的所有數 */
    {
        if (_number % i == 0)
        {
            return 0;               /* 若可以被整除,則不是質數,返回 0 */
        }
    }

    return 1;       /* 若執行完以上程式均未返回,則是指數,返回 1 */
}

巧用平方根

使用暴力求解固然可以求出一個數是否為質數,但運算次數是最多的,運行速度也是最慢的,我們還可以將程式進行優化,提升程式運行時的效率。

在一般領域,對正整數 number,如果用 2 到 $\sqrt{number}$ 之間的所有整數去除,均無法整除,則 number 為質數。那麼就可以利用這一方法,巧用平方根判斷一個數是否為質數。

在 C 語言中求平方根可以使用 C 標準庫,<math.h> 頭文件中定義了各種數學函數,sqrt() 函數是平方根函數,功能是計算一個非負實數的平方根,調用時程式要包含 <math.h> 頭文件。

具體代碼如下:

/****************************************************************************
* 函數名:  Judge_PrimeNumber
* 功能描述:判斷一個數是否為質數
* 輸入參數:
*			_number:需要判斷的數
* 返回值:
*			1:是質數
*			0:不是質數
* 外部參數:無
* 註意事項:無
*
* 作者:	梁國慶
* 日期:	2021-12-11
* 修改記錄:
****************************************************************************/
int Judge_PrimeNumber(int _number)
{
    int i = 0;

    if (_number < 2)
    {
        return 0;   /* 需要判斷的數小於 2,則不是質數,返回 0 */
    }

    for (i = 2; i <= sqrt(_number); i++)    /* 遍歷從 2 到 √_number 區間中的所有數 */
    {
        if (_number % i == 0)
        {
            return 0;                       /* 若可以被整除,則不是質數,返回 0 */
        }
    }

    return 1;       /* 若執行完以上程式均未返回,則是指數,返回 1 */
}

如何調用函數

對於如何使用 C 語言判斷質數,共講解了兩種方法並分別將編寫的程式封裝成為函數,現在我們來講解一下如何在實際應用中調用它們。

在這裡,我以巧用平方根為例進行講解(暴力求解的調用方法與之相同),也特別推薦大家在以後的使用中優先選擇巧用平方根這種方法,因為通過平方根進行判斷是運算次數最少的,可以極大的提高我們程式的效率。

樣例代碼中,我們輸入一個整數,然後調用判斷質數的函數,若輸入的數是質數則輸出 Yes,否則輸出 No

具體代碼如下:

#include <stdio.h>
#include <math.h>   /* 包含 <math.h> */

/****************************************************************************
* 函數名:  Judge_PrimeNumber
* 功能描述:判斷一個數是否為質數
* 輸入參數:
*			_number:需要判斷的數
* 返回值:
*			1:是質數
*			0:不是質數
* 外部參數:無
* 註意事項:無
*
* 作者:	梁國慶
* 日期:	2021-12-11
* 修改記錄:
****************************************************************************/
int Judge_PrimeNumber(int _number)
{
    int i = 0;

    if (_number < 2)
    {
        return 0;   /* 需要判斷的數小於 2,則不是質數,返回 0 */
    }

    for (i = 2; i <= sqrt(_number); i++)    /* 遍歷從 2 到 √_number 區間中的所有數 */
    {
        if (_number % i == 0)
        {
            return 0;                       /* 若可以被整除,則不是質數,返回 0 */
        }
    }

    return 1;       /* 若執行完以上程式均未返回,則是指數,返回 1 */
}

int main()
{
    int N = 0;

    scanf("%d", &N);

    if (Judge_PrimeNumber(N) == 1)  /* 調用判斷質數的函數,判斷輸入的整數 N */
    {
        printf("Yes\n");            /* 是質數,則輸出 Yes */
    }
    else
    {
        printf("No\n");             /* 否則輸出 No */
    }

    return 0;
}

後記

至此,我們講解了關於質數的定義,帶領大家編寫了 C 語言判斷質數的程式代碼,並將所寫代碼封裝成為函數,同時為大家演示瞭如何調用函數來判斷質數。
相信看完本篇文章的你,以後再遇到 C 語言判斷質數的問題,可以解決的游刃有餘。

本文作者:main工作室

本文鏈接:https://www.cnblogs.com/main-studio/p/17064035.html

版權聲明:本文為「main工作室」的原創文章,遵循 CC BY-NC-ND 4.0 版權協議,著作權歸作者所有,轉載請註明出處!

鼓勵博主:如果您覺得文章對您有所幫助,可以點擊文章右下角【推薦】一下。您的鼓勵就是博主最大的動力!


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

-Advertisement-
Play Games
更多相關文章
  • 寫在前面 在開發的過程中,大多數人都需要對代碼進行測試。目前對於c/c++項目,可以採用google的gtest框架,除此之外在github上搜索之後可以發現很多其他類似功能的項目。但把別人的輪子直接拿來用,終究比不過自己造一個同樣功能的輪子更有成就感。作為“linux環境編程”系列文章的第一篇,本 ...
  • 基於 LGT8F328P LQFP32 的 Arduino Mini EVB, 這個板型資料較少, 記錄一下開發環境和燒錄過程以及當中遇到的問題. ...
  • 介紹一些我常用的ssh工具 1、Xshell ​ Xshell應該是一款家喻戶曉的ssh連接工具,本人有幸也在很長一段時間都在使用Xshell,但是Xshell他是收費的!而且每次關閉後都會有一個提示框,我很不喜歡,而且Xshell的ftp或其他插件都是需要額外自行下載的,對於文件傳輸不太方便,但是 ...
  • JavaScript 中的作用域指的是變數和函數的可訪問範圍。 JavaScript 中,閉包是一個函數對象,它可以訪問定義該函數的作用域里的變數,即使函數已經返回。閉包的特點是,它可以在其相關環境不存在時保留變數。閉包可以被保存到變數中併在以後使用。它具有兩個特征,一是可以訪問外部函數的變數,二是... ...
  • JavaScript 中的 this 關鍵字引用了所在函數正在被調用時的對象。在不同的上下文中,this 的指向會發生變化。可以通過 call, apply, bind 方法來改變 this 的上下文。 ...
  • 一群高智商青年在餐廳吃飯,餐桌上一個瓶蓋標識為鹽的瓶子里裝得是胡椒粉,而標識為胡椒粉的瓶子里裝得卻是鹽,他們想出了一個充滿才氣的方案來完成對調--僅需要一張餐巾紙、一根吸管和兩個空碟子。當他們叫來服務員,準備炫耀他們的天才想法時,只見服務員什麼也沒說,只是拿起鹽瓶和胡椒粉瓶,互換了瓶蓋…… 在我們... ...
  • 2023-01-21 一、攔截器與過濾器的區別 1、過濾器(Filter)屬於web伺服器組件 (1)過濾器主要作用:過濾Servlet請求 (2)執行時機:兩處執行時機(Servlet前、Servlet後) 2、攔截器(Interceptor)屬於框架(springMVC) (1)攔截器主要作用: ...
  • Spring管理Bean-IOC-05 3.基於註解配置bean 3.3自動裝配 基本說明: 基於註解配置bean,也可以實現自動裝配,使用的註解是:@AutoWired或者@Resource @AutoWired 的規則說明 (1)在IOC容器中查找待裝配的組件的類型,如果有唯一的bean裝配(按 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...