2013年复试程序设计题

最新推荐文章于 2023-03-24 21:53:44 发布

GanonYou

最新推荐文章于 2023-03-24 21:53:44 发布

阅读量2.2k

点赞数 4

分类专栏：算法 C++

本文链接：https://blog.csdn.net/qq_32925781/article/details/79410775

版权

2013年

1. 编写程序,计算 1~20000 之间的质数,输出时要求每行 10 个数。

穷举的代码就不贴出了，下面给出一个时间复杂度O(n)的方法：
质数是从2开始讨论的，不妨先假设所有数都是质数，而任何一个数(包括质数)的 n(n>1) 倍一定不是质数，所以每访问一个数，就把它所有的n倍置为非质数。我们用一个vector< bool > numbers来保存所有数的情况，质数为true，非质数为false。

下面贴代码：

#include <iostream>
#include <vector>
using namespace std;

#define MAX_SIZE 20000

void getPrime(vector<bool> &numbers,vector<int> &primes){
    for (int i = 2; i <= MAX_SIZE; i++) {     //质数是从2开始讨论的
        if (numbers[i] == true)      //如果是质数，放入primes向量
            primes.push_back(i);

        for (int j = i; j <= MAX_SIZE; j += i)      //任何一个数的n倍一定不是质数，全部置为false
            numbers[j] = false;
    }
}

int main(){

    vector<bool> numbers(MAX_SIZE,true);       //初始化，默认都是质数true
    vector<int> primes;

    getPrime(numbers, primes);

    int count = 0;
    for (vector<int>::iterator it = primes.begin();it != primes.end() ;it++){
        cout << *it << " ";
        count++;
        if (count == 10){
            cout << endl;
            count = 0;
        }
    }

    cout << endl;
    return 0;
}