Why is this code not working for big number?

Question

I'm doing question 4.11 in Bjarne Stroustrup Programming-Principles and Practice Using C++. Create a program to find all prime numbers in the range from 1 to max using a vector of primes in order(prime[2,3,5,...]). Here is my solution:

#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 << ',';
  }
}

My code is working for numbers smaller than 23 but fail to work for anything bigger. If I open the program in Windows 10 the largest working number increase to 47, anything bigger than that fail to work.

Please check [this](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) and also [this](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). — Blaze, Nov 20 '19 at 13:23
is Bjarne suggeting to use `using namespace std;` and `#include ` ? I could forgive him on the former but not on the latter. — 463035818_is_not_an_ai, Nov 20 '19 at 13:23
What is your OS / Hardware and compiler version ? What is the exact error you get ? — Clonk, Nov 20 '19 at 13:24
Is the condition in `for(int i=0;prime[i]<=n||i<=prime.size()-1;++i) {` correct ? — Arne J, Nov 20 '19 at 13:26
[How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — PaulMcKenzie, Nov 20 '19 at 13:33
Unrelated to issue but you got rather hard to read logic how to write "return count == 0;" — Öö Tiib, Nov 20 '19 at 13:37
Please note that adding some spaces and newlines would increase your code readability. — Bob__, Nov 20 '19 at 13:41

score 1 · Answer 1 · answered Nov 20 '19 at 13:28

1

You check prime[i]<=n before i<=prime.size()-1. Then, if it's true (even if i>prime.size()-1, which is random behaviour), you work on it, generating wrong results.

answered Nov 20 '19 at 13:28

Caduchon

4,574
4
26
67

score 1 · Accepted Answer · answered Nov 20 '19 at 13:36

This condition

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

makes the loop continue as long as at least one of them is true, and you're accessing prime[i] without checking the value of i.
This will cause undefined behaviour as soon as i == prime.size().
This means that anything can happen, and that you're experiencing that any specific values are working is just an unfortunate coincidence.

You need to check the boundary first, and you should only continue for as long as both conditions are true:

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

which is more idiomatically written

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

(It's never too soon to get comfortable with the conventional half-open intervals.)

Thanks. I look at it for half an hour and didnt notice that I use || instead of &&. And somehow it works for small max number which confused me greatly. — Cuong, Nov 20 '19 at 13:48

Why is this code not working for big number?

2 Answers2