c++高效方法输出2-100之间的质数
时间: 2024-02-12 08:07:11 浏览: 78
以下是使用高效方法输出2-100之间的质数的C++代码:
```c++
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
int main()
{
cout << "2-100之间的质数有:";
for (int i = 2; i <= 100; i++) {
if (isPrime(i))
cout << i << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
2-100之间的质数有: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
```
这里使用了质数的判断方法叫做“试除法”,在判断一个数n是否为质数时,只需要用小于等于sqrt(n)的质数进行试除即可,因为如果n不是质数,那么一定可以分解为两个因数p和q,其中p<=sqrt(n),q>=sqrt(n),而试除法就是在2到sqrt(n)之间进行试除。
阅读全文