一文解決如何使用 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
  • 背景 在瀏覽器中訪問本地靜態資源html網頁時,可能會遇到跨域問題如圖。 是因為瀏覽器預設啟用了同源策略,即只允許載入與當前網頁具有相同源(協議、功能變數名稱和埠)的內容。 WebView2預設情況下啟用了瀏覽器的同源策略,即只允許載入與主機相同源的內容。所以如果我們把靜態資源發佈到iis或者通過node ...
  • 最近看幾個老項目的SQL條件中使用了1=1,想想自己也曾經這樣寫過,略有感觸,特別拿出來說道說道。編寫SQL語句就像炒菜,每一種調料的使用都會影響菜品的最終味道,每一個SQL條件的加入也會影響查詢的執行效率。那麼 1=1 存在什麼樣的問題呢?為什麼又會使用呢? ...
  • 好久不見,我又回來了。 給大家分享一個我最近使用c#代碼操作ftp伺服器的代碼示例: 1 public abstract class FtpOperation 2 { 3 /// <summary> 4 /// FTP伺服器地址 5 /// </summary> 6 private string f ...
  • 一:背景 1. 講故事 過年喝了不少酒,腦子不靈光了,停了將近一個月沒寫博客,今天就當新年開工寫一篇吧。 去年年初有位朋友找到我,說他們的系統會偶發性崩潰,在網上也發了不少帖子求助,沒找到自己滿意的答案,讓我看看有沒有什麼線索,看樣子這是一個牛皮蘚的問題,既然對方有了dump,那就分析起來吧。 二: ...
  • 自己製作的一個基於Entity Framework Core 的資料庫操作攔截器,可以列印資料庫執行sql,方便開發調試,代碼如下: /// <summary> /// EF Core 的資料庫操作攔截器,用於在資料庫操作過程中進行日誌記錄和監視。 /// </summary> /// <remar ...
  • 本文分享自華為雲社區《Go併發範式 流水線和優雅退出 Pipeline 與 Cancellation》,作者:張儉。 介紹 Go 的併發原語可以輕鬆構建流數據管道,從而高效利用 I/O 和多個 CPU。 本文展示了此類pipelines的示例,強調了操作失敗時出現的細微之處,並介紹了乾凈地處理失敗的 ...
  • 在上篇文章中,我們介紹到在多線程環境下,如果編程不當,可能會出現程式運行結果混亂的問題。出現這個原因主要是,JMM 中主記憶體和線程工作記憶體的數據不一致,以及多個線程執行時無序,共同導致的結果。 ...
  • 1、下載安裝包首先、進入官網下載安裝包網址:https://www.python.org/downloads/windows/下載步驟:進入下載地址,根據自己的電腦系統選擇相應的python版本 選擇適配64位操作系統的版本(查看自己的電腦操作系統版本), 點擊下載安裝包 也可以下載我百度雲分享的安 ...
  • 簡介 git-commit-id-maven-plugin 是一個maven 插件,用來在打包的時候將git-commit 信息打進jar中。 這樣做的好處是可以將發佈的某版本和對應的代碼關聯起來,方便查閱和線上項目的維護。至於它的作用,用官方說法,這個功能對於大型分散式項目來說是無價的。 功能 你 ...
  • 序言 在數字時代,圖像生成技術正日益成為人工智慧領域的熱點。 本討論將重點聚焦於兩個備受矚目的模型:DALL-E和其他主流AI繪圖方法。 我們將探討它們的優勢、局限性以及未來的發展方向。通過比較分析,我們期望能夠更全面地瞭解這些技術,為未來的研究和應用提供啟示。 Q: 介紹一下 dall-e Ope ...