### Problem with prime numbers

Guys i'm in a debacle. Why can't i find prime numbers more than 100.. I think my logic is perfect. My algorithm showed every prime numbers from 1-100 but my program does not work if i tried to find all primes from 1 - 1000. It just stops and would not allow me to start my program. Is it not allowed to find all prime numbers?

 ``123456789101112131415161718192021222324252627282930313233343536373839`` ``````#include #include #include using namespace std; int main() { vector prime(1); prime[0] = 2; int primo = 0; for(int i = 2; i <= 200; i++){ bool isPrime = false; if(i % 2 == 1) { int odd; odd = i; for(int t = 0; t < prime.size() + 1; t++) { if(t == prime.size()) { primo = odd; isPrime = !isPrime; } else if(odd % prime[t] == 0) t = prime.size(); } if(isPrime) prime.push_back(primo); } else continue; } for(int i = 0; i < prime.size(); i++) { cout << prime[i] << endl; Sleep(350); } system("pause>0"); return 0; } ``````

As you can see my logic is, if a number is not divisible by 2 and not divisible by any other primes then it's a prime or is my logic wrong also?

EDIT: I used it in window so i have included <windows.h>
Last edited on
At lines 11 and 12 the the for-loop is giving ` t` a value bigger than the vector size, and accessing elements which do not exist. The code is not valid.
Right i forgot that i gave it a `<=` on line 11.
Should have been `<`

But my problem still remains.. it works if i find 1-100 prime but crashes if i try to find 1-101 or greater..
OK, but you also had at line 11 ` prime.size() + 1` which also contributes to the problem, did you fix that too?
the end of the for loop will increment `t` so it will be equal to `prime.size() + 1`

so yeah it's fix
so at line 12 you will access element prime[t] where t == prime.size(). That is invalid, you need the loop similar to that at line 26:
`for(int i = 0; i < prime.size(); i++) {`
Last edited on
line 11 for loop will continue from 0 to no. of element of vector..
at line 12..
 ``12`` ``````if(odd % prime[t] == 0) t = prime.size();``````

this checks if the number is divisible by all listed prime in the vector if the number is found to be divisible by a prime then i set the value of `t = prime.size()`
then before the for loop ends will increment `t` so `t < prime.size() + 1` will become false because `t` is now equal to `prime.size() + 1` so it will not enter the loop and thus will not access the out of bound vector element.. I'm sorry if i still don't agree but if i did that would mean that my understanding of how the for-loop work is wrong all this time.

but `for(int i = 0; i < prime.size(); i++) {` still works so yeah.. :D
Last edited on
closed account (NyqLy60M)
The problem is that you're trying to reference prime[t] where t is the size of your vector at one point (one element larger than what is defined, because the first element is referenced through 0).

And just a side-note, C++ 11 allows containers to be initialized like C-style arrays, so you can do something like:
 `` `` ``vector prime = {3}; // prime.at(0) == 3 ``
Yeah.. for line 11 i already changed it to `<` rather than keep it at `<=`.. And for the initialization i know that it could be than in arrays but wasn't sure with vectors.. This is actually my first code using vectors, i usually use arrays.. Vectors are quite useful.
The fix is quite simple.

Let's look at your code right now:
 ``111213141516171819`` ``````for(int t = 0; t < prime.size() + 1; t++) { if(odd % prime[t] == 0) t = prime.size(); else if(t == prime.size()) { primo = odd; isPrime = !isPrime; } }``````

Notice that the last value of t will be equal to prime.size().
However, in the first `if` statement, you try to access prime[t], which is out-of-bounds.

Therefore, you will want to first check for `t == prime.size()`:
 ``111213141516171819`` ``````for(int t = 0; t < prime.size() + 1; t++) { if(t == prime.size()) { // Check this first primo = odd; isPrime = !isPrime; } else if(odd % prime[t] == 0) t = prime.size(); }``````

Also, on line 29:
`system("pause>0");`
Besides the fact that using system generally isn't recommended, this line should probably actually be
`system("pause>nul");`.
Otherwise, you end up creating a file named "0" in the current directory....
@long double main yeah thanks for the info..

 ``1234567`` ``````for(int t = 0; t < prime.size() + 1; t++) { if(odd % prime[t] == 0) t = prime.size(); else if(t == prime.size()) { primo = odd; isPrime = !isPrime; }``````

but this actually works in my compiler, i'm using dev c++ and i heard that VStudio 2008 or higher does not allow out of bounds elements..

but i will correct my program.

EDIT: and for some reason if i remove the +1 in `for(int t = 0; t < prime.size() + 1; t++)` it does not work for some reason..
Last edited on
Yeah i revised it and took you advice. This is my final code with great accuracy i checked them all my self.. form 1 - 10000.

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647`` ``````#include #include #include using namespace std; int main() { vector prime(1); prime[0] = 2; int primo = 0; int elem; cout << "From what range to you want to find the primes? "; while(!(cin >> elem)) { cin.clear(); cin.ignore(); cout << "Invalid input. Must be an integer" << endl << endl; } for(int i = 2; i <= elem; i++){ bool isPrime = false; if(i % 2 == 1) { int odd; odd = i; for(int t = 0; t < prime.size() + 1; t++) { if(t == prime.size()) { primo = odd; isPrime = !isPrime; } else if(odd % prime[t] == 0) t = prime.size(); } if(isPrime) prime.push_back(primo); } else continue; } for(int i = 0; i < prime.size(); i++) { cout << prime[i] << endl; Sleep(50); } cout << "The number of primes found from 1 to " << elem << " is " << prime.size() << endl; system("pause>0"); return 0; }``````
I see this thread is now marked as resolved; that's ok. But while I'm here, i wanted to mention that the code looked a bit unnecessarily complex, for example variables `primo` and `odd` are not needed, since they both are set to the same value as `i`.

Also, rather than looping through all values of i, and testing whether or not it is an odd number, it is simpler to loop through only the odd numbers.

My suggestion is to replace this code:
 ``2021222324252627282930313233343536373839`` `````` for(int i = 2; i <= elem; i++){ bool isPrime = false; if(i % 2 == 1) { int odd; odd = i; for(int t = 0; t < prime.size() + 1; t++) { if(t == prime.size()) { primo = odd; isPrime = !isPrime; } else if(odd % prime[t] == 0) t = prime.size(); } if(isPrime) prime.push_back(primo); } else continue; }``````

with the following:
 ``20212223242526272829303132333435`` `````` for (int i = 3; i <= elem; i+=2) { bool isPrime = true; for (unsigned int t = 1; t < prime.size(); t++) { if (i % prime[t] == 0) { isPrime = false; break; } } if (isPrime) prime.push_back(i); }``````
Last edited on
Thx for the additional info.. That basically reduces the process by half the time.
Topic archived. No new replies allowed.