Sieve of Eratosthenes-Runtime error!

[hunter86bg]

The task is to create a program that points out all prime numbers within the range of 0-100 using the Sieve of Eratothenes. Since the beginning of the text book i have studied: vectors,strings,if,switch,for and while. Arrays are not covered yet and i'm not supposed to use them.My idea is to create a vector named sequence initialized to 1.Later i take the first prime which is the number :2. Then i multiply the prime number to the rest of all the numbers in the sequence. Each multiplied number will be initiated to integer :0.Then i proceed to the next prime number and so on. After that i add all numbers in the sequence which are initialized as 1 and transfer them to another vector "isprime" and then print it out."std_lib_facilities.h" is designed to help in the beginning.
I don't have compile time errors but run-time.I have searched but i don't see anything.
Here is my code:

/* Sieve of eratosthenes project for finding primes
up to 100 */
#include <../../std_lib_facilities.h>

int main()
{
	int sum=0;
	int max=100;
	vector<int>sequence(max,1);
	sequence[0]=0; sequence[1]=0;
	vector<int>isprime;
	
		for(int i=2; i<max;++i){
		 if (isprime[i]==1)
			 for(int x=0;x<max;++x){
				 sum = i * (i+x);
				 if(sum*sum<max)
					 sequence[sum]=0;
				 sum=0;
			 }
		}


	for(int z=0;z<max;++z){
		if (sequence[z]==1)
			isprime.push_back(z);
	}
		for(int i=0;i<isprime.size();++i)
			cout << "Prime number: " << isprime[i]<<endl;
		
	return 0;
}

/*
	simple "Programming: Principles and Practice using C++" course header to
	be used for the first few weeks.
	It provides the most common standard headers (in the global namespace)
	and minimal exception/error support.

	Students: please don't try to understand the details of headers just yet.
	All will be explained. This header is primarily used so that you don't have
	to understand every concept all at once.

	Revised April 25, 2010: simple_error() added
*/

#ifndef H112
#define H112 201004L

#include<iostream>
#include<fstream>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<list>
#include<vector>
#include<algorithm>
#include<stdexcept>

//------------------------------------------------------------------------------

#ifdef _MSC_VER
#include <hash_map>
using stdext::hash_map;
#else
#include <ext/hash_map>
using __gnu_cxx::hash_map;

namespace __gnu_cxx {

    template<> struct hash<std::string>
    {
        size_t operator()(const std::string& s) const
        {
            return hash<char*>()(s.c_str());
        }
    };

} // of namespace __gnu_cxx
#endif

//------------------------------------------------------------------------------

#define unordered_map hash_map

//------------------------------------------------------------------------------

typedef long Unicode;

//------------------------------------------------------------------------------

using namespace std;

template<class T> string to_string(const T& t)
{
	ostringstream os;
	os << t;
	return os.str();
}

struct Range_error : out_of_range {	// enhanced vector range error reporting
	int index;
	Range_error(int i) :out_of_range("Range error: "+to_string(i)), index(i) { }
};


// trivially range-checked vector (no iterator checking):
template< class T> struct Vector : public std::vector<T> {
	typedef typename std::vector<T>::size_type size_type;

	Vector() { }
	explicit Vector(size_type n) :std::vector<T>(n) {}
	Vector(size_type n, const T& v) :std::vector<T>(n,v) {}
	template <class I>
	Vector(I first, I last) :std::vector<T>(first,last) {}

	T& operator[](unsigned int i) // rather than return at(i);
	{
		if (i<0||this->size()<=i) throw Range_error(i);
		return std::vector<T>::operator[](i);
	}
	const T& operator[](unsigned int i) const
	{
		if (i<0||this->size()<=i) throw Range_error(i);
		return std::vector<T>::operator[](i);
	}
};

// disgusting macro hack to get a range checked vector:
#define vector Vector

// trivially range-checked string (no iterator checking):
struct String : std::string {
	
	String() { }
	String(const char* p) :std::string(p) {}
	String(const string& s) :std::string(s) {}
	template<class S> String(S s) :std::string(s) {}
	String(int sz, char val) :std::string(sz,val) {}
	template<class Iter> String(Iter p1, Iter p2) : std::string(p1,p2) { }

	char& operator[](unsigned int i) // rather than return at(i);
	{
		if (i<0||size()<=i) throw Range_error(i);
		return std::string::operator[](i);
	}

	const char& operator[](unsigned int i) const
	{
		if (i<0||size()<=i) throw Range_error(i);
		return std::string::operator[](i);
	}
};

#ifndef _MSC_VER
namespace __gnu_cxx {

    template<> struct hash<String>
    {
        size_t operator()(const String& s) const
        {
            return hash<std::string>()(s);
        }
    };

} // of namespace __gnu_cxx
#endif


struct Exit : runtime_error {
	Exit(): runtime_error("Exit") {}
};

// error() simply disguises throws:
inline void error(const string& s)
{
	throw runtime_error(s);
}

inline void error(const string& s, const string& s2)
{
	error(s+s2);
}

inline void error(const string& s, int i)
{
	ostringstream os;
	os << s <<": " << i;
	error(os.str());
}

#if _MSC_VER<1500
	// disgusting macro hack to get a range checked string:
	#define string String
	// MS C++ 9.0 have a built-in assert for string range check
	// and uses "std::string" in several places so that macro substitution fails
#endif

template<class T> char* as_bytes(T& i)	// needed for binary I/O
{
	void* addr = &i;	// get the address of the first byte
						// of memory used to store the object
	return static_cast<char*>(addr); // treat that memory as bytes
}


inline void keep_window_open()
{
	cin.clear();
	cout << "Please enter a character to exit\n";
	char ch;
	cin >> ch;
	return;
}

inline void keep_window_open(string s)
{
	if (s=="") return;
	cin.clear();
	cin.ignore(120,'\n');
	for (;;) {
		cout << "Please enter " << s << " to exit\n";
		string ss;
		while (cin >> ss && ss!=s)
			cout << "Please enter " << s << " to exit\n";
		return;
	}
}



// error function to be used (only) until error() is introduced in Chapter 5:
inline void simple_error(string s)	// write ``error: s’’ and exit program
{
	cerr << "error: " << s << '\n';
	keep_window_open();		// for some Windows environments
	exit(1);
}

// make std::min() and std::max() accessible:
#undef min
#undef max

#include<iomanip>
inline ios_base& general(ios_base& b)	// to augment fixed and scientific
{
	b.setf(ios_base::fmtflags(0),ios_base::floatfield);
	return b;
}

// run-time checked narrowing cast (type conversion):
template<class R, class A> R narrow_cast(const A& a)
{
	R r = R(a);
	if (A(r)!=a) error(string("info loss"));
	return r;
}


inline int randint(int max) { return rand()%max; }

inline int randint(int min, int max) { return randint(max-min)+min; }

inline double sqrt(int x) { return sqrt(double(x)); }	// to match C++0x

#endif 

[cire]

	vector<int>isprime;
	
		for(int i=2; i<max;++i){
		 if (isprime[i]==1)

Your vector is empty. You treat it as if it's not.

If you change the definition of isprime to:

vector<int>isprime(100) // create a vector with 100 elements

that will no longer be a source of problems.

[hunter86bg]

I just found it ... actually it should be read as:
if (sequence[i]==1)

[hunter86bg]

Ok i will post the working version of the Sieve of Eratosthenes for everyone who is interested in it :

/* Sieve of eratosthenes project for finding primes
up to 100 */
#include <../../std_lib_facilities.h>


int main()
{
	int sum=0;
	int max=100;
	cout <<"Enter max number: \t";
	cin >> max;
	vector<int>sequence(max,1);
	sequence[0]=0; sequence[1]=0;
	vector<int>primes;
	
		for(int i=2; i<max;++i){
		 if (sequence[i]==1)
			 for(int x=2;x<max;++x){
				 sum = i * x;
				 if (sum < max)
						sequence[sum]=0;
						sum=0;
			 }
		}


	for(int z=0;z<max;++z){
		if (sequence[z]==1)
			primes.push_back(z);
	}
		for(int i=0;i<primes.size();++i)
			cout << "Prime number: " << primes[i] <<endl;
		
	return 0;
}

The "std_lib_facilities.h" remains the same.

[3TXyhbRD]

Lines 21 and 22 are supposed to be executed if (sum < max)? If so you have a bug (even if it's not supposed to be executed you still have a logical error there).

I like the fact that you work with STL (vector) however you don't use iterators. For instance, your for could look like (C++11):

for(auto it = isprime.begin(), end = isprime.end(); it != end; it++)
    cout << *it << endl;

Of course for vectors the difference is slim, however think about a linked list. The access is no longer direct unless an iterator is used.

When I see isprime I think that that vector says whether the number equal with the index is prime or not. E.g.: isprime[2] tells if 2 is prime or not. But in your code I see that isprime contains a list of primes and I have a small logic implosion in my head.

The loop where you determine the sequence of primes could do a little work (besides the bug mentioned above).

PS: For the sake of our eyes, format your code better. Thank you...

[hunter86bg]

1)Well if you dont have the check if (sum < max) you will ask sequence [sum] to be marked as 0. Which can't happen as vector <int> sequence is initialised to number max , so sequence[sum] will not be part of the vector ... For example i= 2,x=60 [ which will be less than 100]... then sum=120 but sequence[120] is non existing.

2)For the "std_lib_facilities.h" I can't comment anything ,because i still don't understand anything in it . I think mister Bjarne Stroustrup made his code to work as supposed- otherwise , i don't know

3)Actually vector sequence - points if a number is prime or not and vector primes contains all the prime numbers in it . Example: sequence[2] = 1 {this means its prime} and later

for(int z=0;z<max;++z){
		if (sequence[z]==1)
			primes.push_back(z);

PS: I checked if the program output gives correct information-It does up to 100 and i have randomly checked prime numbers above this limit and it still points prime numbers. If you have some idea to optimize the code - please be my guest.

[3TXyhbRD]

1) That's not what I asked.

2) It's okay, look into STL bit by bit when you can. It's has lots of features.

3) That's exactly what I said. If isprime contains all prime numbers then it's name should be primes. sequence should be renamed to isprime. It's just a naming thing that will make your code make more sense when someone else reads it.

PS: if you have a vector that takes values 0 and 1. You can consider using the type bool, just a thought.

[hunter86bg]

Ok i will edit the code from isprime to primes.
I thought of the bool type but i wasn't sure if true = 1 or true =0. I'm still revising the text book - i haven't opened it for an year.
Thanks for your comments. I know i should have put some comments explaining the source.

[3TXyhbRD]

hunter86bg wrote:

Thanks for your comments. I know i should have put some comments explaining the source.

No. The code has to explain itself. If you place comments it means that the code is to complicated already. How to organize your code comes from personal experience and it takes time. Some online guidelines may help, but it's up to how you code and how you go at the problem.

It's easy to test whether true is 1 or not, however it may seem logic what value it holds since anything after if (true) has to be executed.

Did you understand what I meant by lines 21 and 22? You still haven't replied on that...

PS: my goal is not to make you change your code because I don't like how you named a few variables. When one reads a source code he should feel like it's telling him what it's doing (just my opinion).

PS2: I hope I haven't made you feel a bit down with all my comments, they're just finishing touches ideas. Think of it as polishing a polished glass.

[Chervil]

It could be a little bit shorter...

/* Sieve of eratosthenes project for finding primes
up to 100 */

#include <iostream>
#include <vector>

    using namespace std;

int main()
{
    int max=100;
    cout <<"Enter max number: \t";
    cin >> max;
    vector<int> sequence(max,1);
    sequence[0]=0; 
    sequence[1]=0;

    for (int i=2; i<max;++i)
        if (sequence[i])
            for (int x=i+i; x<max; x+=i)
                sequence[x] = 0;

    for (int z=0;z<max;++z)
        if (sequence[z])
            cout << "Prime number: " << z <<endl;

    return 0;
}

[hunter86bg]

I hope I haven't made you feel a bit down with all my comments, they're just finishing touches ideas. Think of it as polishing a polished glass.

I don't see any problem in that - after all that is the point of the forums. I know I'm still newbie but I try to learn.
Chervil, I have compiled your code and it seems to do the job and be quite easier to understand.
Thank you both for your help.