素數(shù)在小學(xué)數(shù)學(xué)也叫質(zhì)數(shù)

方法：所謂素數(shù)是指除了1和它本身以外，不能被任何整數(shù)整除的數(shù)，例如17就是素數(shù)，因為它不能被2~16的任一整數(shù)整除。因此判斷一個整數(shù)m是否是素數(shù)，只需把m被2~m-1之間的每一個整數(shù)去除，如果都不能被整除，那么m就是一個素數(shù)。

另外判斷方法還可以簡化。m不必唄2~m-1之間的每一個整數(shù)去除，只需被2~√m之間的每一個整數(shù)去除就可以了。如果m不能被2~√m間任一整數(shù)整除，m必定是素數(shù)。例如判別17是是否為素數(shù)，只需使17被2~4之間的每一個整數(shù)去除，由于都不能整除，可以判定17是素數(shù)。

C++程序如下：

#include<iostream>
#include<cmath> //引用了數(shù)學(xué)函數(shù)平方根：sqrt（）
using namespace std;

bool isprime(int x)
{
if(x==0||x==1) return 0; //將特殊情況0和1單獨拿出來進行
for (int i=2;i<=sqrt(x)+0.5;i++) // 想想為何+0.5？因為假如sqrt(9)返回2.999999999，n＝2，結(jié)果可就錯了。
if (x%i==0) return false;
return true;
}

int main()
{
freopen("p.in","r",stdin);
freopen("p.out","w",stdout); //習(xí)慣用文件輸入與輸出，不明白的可參與相關(guān)資料
int x;
cin>>x;
cout<<isprime(x)<<endl; //0表示不是素數(shù)，非0表示是素數(shù)

return 0;
}

在實際編程中，如果每個數(shù)都要判斷是否是素數(shù)，采用上面的算法，時間復(fù)雜度會很大。這時就采用素數(shù)表，一下子就簡化了時間復(fù)雜度。

方法如下：篩法產(chǎn)生素數(shù)表

實現(xiàn)程序如下：

總結(jié)

以上是生活随笔為你收集整理的判断素数与产生素数表（质数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。