c++ - 如何将质数放入 vector 中？

Question

我在下面写了一段代码，要求用户输入并检查它是否为质数。我现在想以此为基础，所以当用户输入一个数字时，我会计算到这个数字的素数并显示。例如，如果用户输入 10，我的程序将输出“有 4 个质数”。我的想法是我必须将每个质数存储到一个 vector 中，但我的问题是如何存储？

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

int main()
{
    vector <double> primeHolder
    int x, i, flag;
    cout << "Enter a positive integer ";
    cin >> x;

    for (i = 2; i <= x/2; i++)
    {
        if(x%i == 0)
        {
            flag = 1;
            break;
        }
    }

    if (flag == 0)
        cout << "This is a prime number";
    else
        cout << "This is not a prime number";
    return 0;
}

Answer 1

首先，定义一个 isPrime() 函数使您的代码更具可读性是有意义的:

bool isPrime(int x)
{
    for(int i = 2; i <= x/2; i++)
    {
        if(x%i == 0)
        {
            return false;
        }
    }
    return true;
}

然后你可以按照下面的方式编写你的main():

int main()
{
    int input;
    cout << "Enter a positive integer: ";
    cin >> input;

    // You deal with integers here, so you shouldn't use vector<double>.
    // As all numbers are positive, you could also use unsigned int.
    vector<int> primeHolder;
    for(int i = 2; i <= input; i++)
    {
        // Test all values that are not larger than the input value.
        if(isPrime(i))
        {
            // If the tested value is a prime, append it to the vector.
            primeHolder.push_back(i);
        }
    }

    cout << "There are " << primeHolder.size() << " primes:" << endl;
    for(size_t j = 0; j < primeHolder.size(); j++)
    {
        // Print every prime number that was stored in the vector.
        // You can access vector elements similar to an array,
        // but you can also use iterators.
        cout << primeHolder[j] << endl;
    }
    return 0;
}

此代码为您的示例输入提供以下输出:

Enter a positive integer: 10
There are 4 primes:
2
3
5
7

注意:上面的代码效率很低。如果你想处理大量输入，你应该寻找更智能的算法，例如Sieve of Eratosthenes ，正如@theoden 在评论中提到的那样。

如果您想了解更多关于vector 类模板的功能，请查看documentation .该文档还包含示例代码。