（一）質(zhì)數(shù)
質(zhì)數(shù)廉赔，又稱為素數(shù)础芍，指在一個大于1的自然數(shù)中低矮，除了1和此整數(shù)自身外，無法被其他自然數(shù)整除的數(shù)（只有1和本身兩個因數(shù)的數(shù)）曹仗。
（二）思路
如果m不能被 2~m的平方根 中的任何一個數(shù)整除榨汤，則m為素數(shù)。
證明（反證法）：
由i = m/i ==> i = sqrt(m)
這樣怎茫，對于i屬于[2, sqrt(m)]收壕，假如i為m的因子妓灌，因為i * m/i = m，則m/i也為m的因子蜜宪。這樣虫埂，m就不是質(zhì)數(shù)。
反過來圃验，對于i屬于[2, sqrt(m)]掉伏，假如所有的i都不為m的因子，因為i * m/i = m澳窑，則m/i也為m的因子斧散。
（三）程序
例1：輸入一個數(shù)，判斷這個數(shù)是否為質(zhì)數(shù)
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int m)
{
if(m > 1)
{
for(int i = 2; i <= sqrt(m); i++)
{
if(0 == m % i)
{
return false;
}
}
return true;
}
return false;
}
int main()
{
int num;
cin >> num;
if(isPrime(num))
{
cout << num << " is a prime" << endl;
}
else
{
cout << num << " is not a prime" << endl;
}
return 0;
}
運行結果：
23
23 is a prime
例2：求1~100之間的全部質(zhì)數(shù)
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int m)
{
if(m > 1)
{
for(int i = 2; i <= sqrt(m); i++)
{
if(0 == m % i)
{
return false;
}
}
return true;
}
return false;
}
int main()
{
for(int i = 2; i <= 100; i++)
{
if(isPrime(i))
{
cout << i << " ";
}
}
return 0;
}
運行結果：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
加入少兒信息學奧賽學習QQ群請掃左側二維碼摊聋，關注微信公眾號請掃右側二維碼
QQ群和公眾號.png
