c++ - Why does my code say 109 is not a prime? -

c++ - Why does my code say 109 is not a prime? -

i trying generate prime numbers , have working reason shows 109 not prime number when 109 prime.

so when output factorcount shows "113 :: 29" when 113 30th prime factor , 107 instead of 109.

#include <iostream> using namespace std; void mark(bool arr[], int a, int n){ int = 2; int num = 0; while((num = i*a) <= n){ arr[num-1] = 1; i++; } } void sieve(int n){ int primecount = 0; if(n >= 2){ bool arr[n]; for(int i=1; i<n; i++){ if(arr[i] == 0){ primecount++; cout << i+1 << " :: " << primecount << endl; mark(arr, i+1, n); } } } } int main(){ int n = 120; sieve(n); homecoming 0; }

your code uses uninitialized variables:

bool arr[n]; for(int i=1; i<n; i++){ if(arr[i] == 0){ // <--- here

you check value of arr[i] when have not set anything.

also, bool arr[n]; illegal in c++ although compilers add together extension. in standard c++, array bounds must known @ compile-time. prepare , alter bool arr[n]; to:

std::vector<unsigned char> arr(n); // note: parentheses, not square brackets

this version zero-initialize members. unfortunately vector<bool> won't work here has unusual specialization. need pass &arr[0] mark, rather arr.

c++