26.计算素数（较差算法）

2021-04-07 19:28

阅读：519

标签：思路 color oid += out end 偶数 names namespace

一. 问题

编写程序，找出1到100之间的所有素数。

二. 思路

1. 用一个 vector 保存当前找到的素数，这个 vector 称为素数表。

2. 对 1 到 100 之间的每一个数，都用这个vector中的素数去除，如果发现能整除，那么说明当前这个数是合数；如果不能整除，那么就说明当前这个数是素数，并把它加入到这个素数表中。

3. 实际上，我们知道 1 不算质数，而 2 是质数，所以我们从 3 开始计算。（即一开始素数表中只有 2 ，后面逐渐往里添加元素）。

三. 代码实现

 1 void find_prime(vectorint> &primes, int n) {
 2     for (int i = 3; i 2) {
 3         bool is_prime = true;
 4         for (auto &x : primes) {
 5             if (i % x == 0) {
 6                 is_prime = false;
 7                 break;
 8             }
 9         }
10         if (is_prime) {
11             primes.push_back(i);
12         }
13     }
14 }

主函数测试：

#include 
#include using namespace std;

int main() {
    vectorint> primes { 2 };
    find_prime(primes, 100);

    for (auto &x : primes) {
        cout " "  endl;
    }
    cout  endl;

    return 0;
}

代码中有几处需要说明：

1. 函数中用一个标识变量 is_prime 来判断当前的数是否质数，因为退出循环时，它可能是素数，也可能不是。

2. 从 3 开始，每次向前进 2 步。因为所有的偶数都不是质数，也就没必要每次进一步了。

26.计算素数（较差算法）

标签：思路 color oid += out end 偶数 names namespace

原文地址：https://www.cnblogs.com/Hello-Nolan/p/13383007.html

上一篇：mro和c3 算法

下一篇：SpringBoot集成Mybatis

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：26.计算素数（较差算法）
文章链接：http://soscw.com/index.php/essay/72537.html

亲，登录后才可以留言！

26.计算素数（较差算法）

评论

热门文章

推荐文章

最新文章

置顶文章