（一）质数
质数，又称为素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（只有1和本身两个因数的数）。
（二）思路
如果m不能被 2~m的平方根 中的任何一个数整除，则m为素数。
证明（反证法）：
由i = m/i ==> i = sqrt(m)
这样，对于i属于[2, sqrt(m)]，假如i为m的因子，因为i * m/i = m，则m/i也为m的因子。这样，m就不是质数。
反过来，对于i属于[2, sqrt(m)]，假如所有的i都不为m的因子，因为i * m/i = m，则m/i也为m的因子。
（三）程序
例1：输入一个数，判断这个数是否为质数
#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之间的全部质数
#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
