一文解決如何使用 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
  • 就像 Web Api 介面可以對入參進行驗證,避免用戶傳入非法的或者不符合我們預期的參數一樣,選項也可以對配置源的內容進行驗證,避免配置中的值與選項類中的屬性不對應或者不滿足預期,畢竟大部分配置都是通過字元串的方式,驗證是很有必要的。 1. 註解驗證 像入參驗證一樣,選項驗證也可以通過特性註解方便地 ...
  • 原文作者:aircraft 原文鏈接:https://www.cnblogs.com/DOMLX/p/17270107.html 加工的泛型類如下: using System; using System.Collections.Generic; using System.IO; using Syst ...
  • 在前一篇文章,我們瞭解瞭如何通過.NET6+Quartz開發基於控制台應用程式的定時任務,今天繼續在之前的基礎上,進一步講解基於ASP.NET Core MVC+Quartz實現定時任務的可視化管理頁面,僅供學習分享使用,如有不足之處,還請指正。 涉及知識點 Quartz組件,關於Quartz組件的 ...
  • 面向對象1 面向對象,更在乎的結果,而過程的實現並不重要 IDea快捷鍵(基礎版) | 快捷鍵 | 作用 | | | | | ctrl + / | 快捷註釋 | | ctrl + shift + / | 多行註釋 | | ctrl + d | 快速複製 | | ctrl + shift + up/d ...
  • NX中的checkmate功能是用於檢查模型、圖紙數據的工具,在UGOPEN中有例子。手動操作可以檢查已載入的裝配下所有零部件,可以設置通過後保存模型,檢查結果保存到Teamcenter中,預設保存在零組件版本下。 代碼中可以設置多個檢查規則。相關設置可以在用戶預設設置中進行設置。 1 // 2 / ...
  • JavaSE 運算符 算術運算符:+,-,*,/,%,++(自增),--(自減) i++:先用後+1;++i:先+1後用 賦值運算符:= 擴展賦值運算符:+=,-=,*=,/= a+=b >a=a+b: ​ 可讀性差,但是編譯效率高,且會自動進行類型轉換; ​ 當ab為基本數據類型時,a+b和b+a ...
  • 面向對象2 訪問修飾符 | | private | default | protected | public | | | | | | | | 當前類 | :heavy_check_mark: | :heavy_check_mark: | :heavy_check_mark: | :heavy_che ...
  • 推薦一些學習qml教程 Qt官方的QML教程: https://doc.qt.io/qt-5/qtqml-index.html 這是一個由Qt官方提供的完整的QML教程,包含了所有基本知識和高級語法。 QML中文網:http://www.qmlcn.com/ 這是一個非常不錯的中文QML學習網站,提 ...
  • QAbstractBUtton: 所有按鈕控制項的基類 提供按鈕的通用功能 繼承自QWidget 屬於抽象類別,不能直接去使用,必須藉助於子類(除非你覺得子類不夠用,想自定義一個按鈕) 大部分功能之前已經使用過,在這裡只作簡單介紹 文本設置: setText(str) :設置按鈕提示文本 text() ...
  • 使用 VLD 記憶體泄漏檢測工具輔助開發時整理的學習筆記。本篇介紹 VLD 配置文件中配置項 StartDisabled 的使用方法。 ...