c++ - 为什么此代码不适用于大数字？

Question

我正在 Bjarne Stroustrup Programming-Principles and Practice Using C++ 中做问题 4.11。
创建一个程序，以按顺序使用素数 vector (素数[2,3,5,...])查找从 1 到最大值范围内的所有素数。这是我的解决方案:

#include <iostream>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
bool check_prime(vector<int> &prime, int n) {
  int count = 0;
  for (int i = 0; prime[i] <= n || i <= prime.size() - 1; ++i) {
    if (n % prime[i] == 0) {
      count++;
      break;
    }
  }
  bool result = 0;
  if (count == 0)
    result = 1;
  else
    result = 0;
  return result;
}

int main() {
  vector<int> prime{2};
  int max;
  cout << "Please enter a max value:";
  cin >> max;
  for (int i = 2; i <= max; ++i) {
    if (check_prime(prime, i))
      prime.push_back(i);
  }
  for (int i = 0; i <= prime.size() - 1; ++i) {
    cout << prime[i];
    if (i <= prime.size() - 2)
      cout << ',';
  }
}

我的代码适用于小于 23 的数字，但无法用于更大的数字。如果我在 Windows 10 中打开程序，最大的工作数量会增加到 47，任何比这更大的都无法工作。

Answer 1

这种情况

prime[i]<=n||i<=prime.size()-1

只要其中至少一个为真，循环就会继续，并且您正在访问 prime[i]不检查 i 的值.
这将尽快导致未定义的行为 i == prime.size() .
这意味着任何事情都可能发生，而您正在体验任何特定的值(value)观正在发挥作用只是一个不幸的巧合。

您需要先检查边界，并且只有在两个条件都为真时才应该继续:

i <= prime.size() - 1 && prime[i] <= n 

哪个写得更地道

i < prime.size() && prime[i] <= n 

(适应传统的半开间隔永远不会太早。)