Problem with prime numbers

[pukol]

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?

#include <iostream>
#include <vector>
#include <windows.h>

using namespace std;

int main()
{
	vector<int> 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>

[Chervil]

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.

[pukol]

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..

[Chervil]

OK, but you also had at line 11 prime.size() + 1 which also contributes to the problem, did you fix that too?

[pukol]

the end of the for loop will increment t so it will be equal to prime.size() + 1

so yeah it's fix

[Chervil]

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++) {

[pukol]

line 11 for loop will continue from 0 to no. of element of vector..
at line 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

[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<int> prime = {3}; // prime.at(0) == 3 

[pukol]

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.

[long double main]

The fix is quite simple.

Let's look at your code right now:

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():

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....

[pukol]

@long double main yeah thanks for the info..

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..

[pukol]

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.

#include <iostream>
#include <vector>
#include <windows.h>

using namespace std;

int main()
{
	vector<int> 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;
}

[Chervil]

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:

    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:

    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);
    }

[pukol]

Thx for the additional info.. That basically reduces the process by half the time.