前言 質數歷來都是數學界的寵兒,是數學里神秘的謎團。 質數又和 C 語言有著不解之緣,本篇文章將講解如何用 C 語言判斷質數。 為了方便大家在讀完此文章後使用文中程式,我會將判斷質數的程式封裝成函數,此函數的功能是:判斷形參 _number 是否是質數,若 _number 是質數,則返回 1;若不是 ...
前言
質數歷來都是數學界的寵兒,是數學里神秘的謎團。
質數又和 C 語言有著不解之緣,本篇文章將講解如何用 C 語言判斷質數。
為了方便大家在讀完此文章後使用文中程式,我會將判斷質數的程式封裝成函數,此函數的功能是:判斷形參 _number
是否是質數,若 _number
是質數,則返回 1
;若不是質數,則返回 0
。
何為質數
質數又稱素數。一個大於 1 的自然數,除了 1 和它自身外,不能被其他自然數整除的數叫做質數;否則稱為合數(規定 1 既不是質數也不是合數)。
C 語言判斷質數
在瞭解了質數的定義後,現在我們便可以著手編寫程式啦。
現在給定一個正整數 number
,要求我們判斷此數是否為質數。針對這一要求本篇採用兩種判斷方法,分別是:暴力求解 與 巧用平方根。
暴力求解
通過質數的定義可以得到如何判斷一個數是否為質數, 我們可以通過遍歷從 2
到 number - 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 版權協議,著作權歸作者所有,轉載請註明出處!
鼓勵博主:如果您覺得文章對您有所幫助,可以點擊文章右下角【推薦】一下。您的鼓勵就是博主最大的動力!