一文解決如何使用 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
  • 一個自定義WPF窗體的解決方案,借鑒了呂毅老師的WPF製作高性能的透明背景的異形視窗一文,併在此基礎上增加了滑鼠穿透的功能。可以使得透明窗體的滑鼠事件穿透到下層,在下層窗體中響應。 ...
  • 在C#中使用RabbitMQ做個簡單的發送郵件小項目 前言 好久沒有做項目了,這次做一個發送郵件的小項目。發郵件是一個比較耗時的操作,之前在我的個人博客裡面回覆評論和友鏈申請是會通過發送郵件來通知對方的,不過當時只是簡單的進行了非同步操作。 那麼這次來使用RabbitMQ去統一發送郵件,我的想法是通過 ...
  • 當你使用Edge等瀏覽器或系統軟體播放媒體時,Windows控制中心就會出現相應的媒體信息以及控制播放的功能,如圖。 SMTC (SystemMediaTransportControls) 是一個Windows App SDK (舊為UWP) 中提供的一個API,用於與系統媒體交互。接入SMTC的好 ...
  • 最近在微軟商店,官方上架了新款Win11風格的WPF版UI框架【WPF Gallery Preview 1.0.0.0】,這款應用引入了前沿的Fluent Design UI設計,為用戶帶來全新的視覺體驗。 ...
  • 1.簡單使用實例 1.1 添加log4net.dll的引用。 在NuGet程式包中搜索log4net並添加,此次我所用版本為2.0.17。如下圖: 1.2 添加配置文件 右鍵項目,添加新建項,搜索選擇應用程式配置文件,命名為log4net.config,步驟如下圖: 1.2.1 log4net.co ...
  • 之前也分享過 Swashbuckle.AspNetCore 的使用,不過版本比較老了,本次演示用的示例版本為 .net core 8.0,從安裝使用開始,到根據命名空間分組顯示,十分的有用 ...
  • 在 Visual Studio 中,至少可以創建三種不同類型的類庫: 類庫(.NET Framework) 類庫(.NET 標準) 類庫 (.NET Core) 雖然第一種是我們多年來一直在使用的,但一直感到困惑的一個主要問題是何時使用 .NET Standard 和 .NET Core 類庫類型。 ...
  • WPF的按鈕提供了Template模板,可以通過修改Template模板中的內容對按鈕的樣式進行自定義。結合資源字典,可以將自定義資源在xaml視窗、自定義控制項或者整個App當中調用 ...
  • 實現了一個支持長短按得按鈕組件,單擊可以觸發Click事件,長按可以觸發LongPressed事件,長按鬆開時觸發LongClick事件。還可以和自定義外觀相結合,實現自定義的按鈕外形。 ...
  • 一、WTM是什麼 WalkingTec.Mvvm框架(簡稱WTM)最早開發與2013年,基於Asp.net MVC3 和 最早的Entity Framework, 當初主要是為瞭解決公司內部開發效率低,代碼風格不統一的問題。2017年9月,將代碼移植到了.Net Core上,併進行了深度優化和重構, ...