What's wrong with my code here? (Sieve of Eratosthenes)

Here is my code (the explanation for what I'm trying to do is all above main() in comments, so please read that first):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// chap4_ex13.cpp : Defines the entry point for the console application.
// Osman Zakir
// 10 / 21 / 2016
// Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 4 Exercise 13
// Find all the primes between 1 and a max value inputted by the user

/* My method for doing this: 
 * Create a vector of the prime numbers between 1 and the square-root of max
 * Create a second vector, this one holding the multiples of the values in the aforementioned vector
 * Iterate in a loop through all values from 2 to max and check each value against the elements
 * in the multiples' vector.  All of the numbers that aren't equal to those multiples are our primes
 * so add those numbers into a separate vector of primes and print it.
 */

#include "std_lib_facilities.h"

int get_max_value();
vector<int> fill_multiples_v(const vector<int>& primes);
vector<int> fill_reg_primes_v(int max);
vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples);
void print_primes(const vector<int>& eratosthenes_primes);
bool is_prime(int number);

int main()
{
	int max = get_max_value();
	vector<int> primes = fill_reg_primes_v(max);
	vector<int> multiples = fill_multiples_v(primes);
	vector<int> eratosthenes_primes = fill_eratosthenes_primes_v(multiples);
	print_primes(primes);
}

int get_max_value()
{
	int max = 0;
	cout << "Enter the value up to which you want to see all prime numbers within the range of:\n";
	cin >> max;
	cin.ignore(32767, '\n');
	return max;
}

vector<int> fill_multiples_v(const vector<int>& primes)
{
	vector<int> multiples;
	for (int i = 2; static_cast<size_t>(i) < primes.size(); ++i)
	{
		if (i % primes[i] == 0)
		{
			multiples.push_back(i);
		}
	}
	return multiples;
}

vector<int> fill_reg_primes_v(int max)
{
	vector<int> primes;
	for (int i = 2, n = sqrt(static_cast<double>(max)); i < n; ++i)
	{
		if (is_prime(i))
		{
			primes.push_back(i);
		}
	}
	return primes;
}

vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples)
{
	vector<int> eratosthenes_primes;
	for (int i = 2; static_cast<size_t>(i) < multiples.size(); ++i)
	{
		if (i != multiples[i])
		{
			eratosthenes_primes.push_back(i);
		}
	}
	return eratosthenes_primes;
}

bool is_prime(int number)
{
	for (int i = 2; i < 100; ++i)
	{
		if (number % i == 0)
		{
			return false;
		}
	}
	return true;
}

void print_primes(const vector<int>& eratosthenes_primes)
{
	for (int i = 0; static_cast<size_t>(i) < eratosthenes_primes.size(); ++i)
	{
		cout << eratosthenes_primes[i] << "\n";
	}
}


So yeah: could someone please tell me why my code doesn't print any numbers? Thanks in advance.
Last edited on
The first thing: your is_prime() function is wrong. Should be:
1
2
3
4
5
6
7
8
9
10
11
bool is_prime(int number)
{
	for (int i = 2; i < number ; ++i)
	{
		if (number % i == 0)
		{
			return false;
		}
	}
	return true;
}

Then, in fill_reg_primes_v(): the evaluation in the for-loop should be: i <= n

By the way, you should add comments to your code, so that a reader like me can mind what your function shall do. So it might be that the other functions are also false, but I don't know what they precisely should do.
*edit*: sorry i have forgotten to read your explaination comment at the top of the file :-(
Last edited on
Don't I have comments above my main() function explaining what my algorithm (if it can be called that) is trying to do? From there, the names of the functions should be self-explanatory.

But anyway, Thanks for the advice on those two functions. I'll try doing what you said and see if it works.

Edit: Well, I got fill_reg_primes_v() and is_prime() to work now. But when I pass my eratosthenes_primes vector from main() to the print_primes() function, then enter 100 as the max value, I get nothing printed.

This is the fill_eratosthenes_primes_v() code:
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples)
{
	vector<int> eratosthenes_primes;
	for (int i = 2; static_cast<size_t>(i) < multiples.size(); ++i)
	{
		if (i != multiples[i])
		{
			eratosthenes_primes.push_back(i);
		}
	}
	return eratosthenes_primes;
}


I'm trying to check if the current number i is not equal to elements inside the multiples vector, and add the numbers to the vector via push_back() if the check is true. But I guess it's not working. Why?

And in case the fill_multiples_v() function also has something wrong with it, here:
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> fill_multiples_v(const vector<int>& primes)
{
	vector<int> multiples;
	for (int i = 2; static_cast<size_t>(i) < primes.size(); ++i)
	{
		if (i % primes[i] == 0)
		{
			multiples.push_back(i);
		}
	}
	return multiples;
}
Last edited on
Your fill_multiples_v() should test all numbers up to 'max', thus your equaluation in the for-loop is wrong. You have to pass the 'max' value for this.

Your exercese has interested me, so I have fixed your whole file. If you're in stuck, look at my fixed version:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// chap4_ex13.cpp : Defines the entry point for the console application.
// Osman Zakir,  (edited by Nico S.)
// 10 / 22 / 2016
// Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 4 Exercise 13
// Find all the primes between 1 and a max value inputted by the user

/* My method for doing this: 
 * 1 Create a vector of the prime numbers between 1 and the square-root of max
 * 2 Create a second vector, this one holding the multiples of the values in the aforementioned vector
 * 3 Iterate in a loop through all values from 2 to max and check each value against the elements
 * in the multiples' vector.  All of the numbers that aren't equal to those multiples are our primes
 * so add those numbers into a separate vector of primes and print it.
 */

// #include "std_lib_facilities.h"
#include <vector>
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int get_max_value();
vector<int> fill_multiples_v(const vector<int>& primes, int max);
vector<int> fill_reg_primes_v(int max);
vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples, int max);
void print_primes(const vector<int>& eratosthenes_primes);
bool is_prime(int number);

int main()
{
    int max = get_max_value();
    vector<int> primes = fill_reg_primes_v(max); // ok
    vector<int> multiples = fill_multiples_v(primes, max);
    vector<int> eratosthenes_primes = fill_eratosthenes_primes_v(multiples, max);
    print_primes(eratosthenes_primes);
}


int get_max_value()
{
    int max = 0;
    cout << "Enter the value up to which you want to see all prime numbers within the range of:\n";
    cin >> max;
    cin.ignore(32767, '\n');
    return max;
}

vector<int> fill_multiples_v(const vector<int>& primes, int max)
{
    vector<int> multiples;
	
    for (int prime : primes)
    {
        for (int number = 2; number <= max; ++number)
        {
            if (number % prime == 0 && number != prime) // prime % prime == 0
            {
                 multiples.push_back( number );
            }
        }
    }
    return multiples;
}

// Up to sqrt(max)
vector<int> fill_reg_primes_v(int max)
{
    vector<int> primes;
    
    for (int i = 2, n = sqrt(static_cast<double>(max)); i <= n; ++i)
    {
        if (is_prime(i))  
        {
            primes.push_back(i);
        }
    }
    return primes;
}

vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples, int max)
{
    vector<int> eratosthenes_primes;

    for (int number = 2; number <= max; ++ number)
    {
        bool is_multiple = false;  // a flag
             
        for (int multiple : multiples)
        {
            if (multiple == number)
            {
                is_multiple = true;
                break;
            }
        }
        if (is_multiple) { continue; }
        eratosthenes_primes.push_back( number );
    }
    return eratosthenes_primes;
}

bool is_prime(int number)
{
    for (int i = 2; i < number ; ++i)
    {
        if (number % i == 0)
        {
            return false;
        }
    }
    return true;
}

void print_primes(const vector<int>& eratosthenes_primes)
{
    for (int prime : eratosthenes_primes)
    {
        cout << prime << "\n";
    }
}

Btw: I learn also from this book, I'm in chapter 20 :-)
Last edited on
I don't think you should give me the whole answer like that. Just tell me this: will it work after I've made the change you mentioned to fill_multiples_v()?

And by the way, for Chapter 4 Exercises 20 and 21 (the ones that say to make modifications to the names and scores program from Exercise 19), these ones:
20. Modify the program from exercise 19 so that when you enter a name, the
program will output the corresponding score or name not found.
21. Modify the program from exercise 19 so that when you enter an integer,
the program will output all the names with that score or score not found.


Could you give me tips for how to do those? Also, would a std::map work for this program? I did Exercise 19 pretty fine without it, but I think it'd be easier with a std::map.

You could help me with that after the current one's done. I also tried the one for solving quadratic equations and for some reason, the value for the discriminant is coming out wrong. I'll probably make a separate thread for that one.

By the way, I'm going through this book for the second time after getting stumped on the exercise for making that program that works as a model for a library's database software. I couldn't get it right. So I decided to go back through the book and read it again. This time I plan to do it again more carefully.

Edit: I tried following yours, but mine now only prints 2 and 3 when I input 100 as the max value. I ran yours with site's shell and it's completely fine.

Here's my code now:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
// chap4_ex13.cpp : Defines the entry point for the console application.
// Osman Zakir
// 10 / 21 / 2016
// Programming: Principles and Practice Using C++ 2nd Edition
// Chapter 4 Exercise 13
// Find all the primes between 1 and a max value inputted by the user

/* My method for doing this: 
 * Create a vector of the prime numbers between 1 and the square-root of max
 * Create a second vector, this one holding the multiples of the values in the aforementioned vector
 * Iterate in a loop through all values from 2 to max and check each value against the elements
 * in the multiples' vector.  All of the numbers that aren't equal to those multiples are our primes
 * so add those numbers into a separate vector of primes and print it.
 */

#include "std_lib_facilities.h"

int get_max_value();
vector<int> fill_multiples_v(const vector<int>& primes, const int max);
vector<int> fill_reg_primes_v(int max);
vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples, int max);
void print_primes(const vector<int>& eratosthenes_primes);
bool is_prime(int number);

int main()
{
	int max = get_max_value();
	vector<int> primes = fill_reg_primes_v(max);
	vector<int> multiples = fill_multiples_v(primes, max);
	vector<int> eratosthenes_primes = fill_eratosthenes_primes_v(multiples, max);
	print_primes(eratosthenes_primes);
}

int get_max_value()
{
	int max = 0;
	cout << "Enter the value up to which you want to see all prime numbers within the range of:\n";
	cin >> max;
	cin.ignore(32767, '\n');
	return max;
}

vector<int> fill_multiples_v(const vector<int>& primes, const int max)
{
	vector<int> multiples;
	for (int prime : primes)
	{
		for (int number = 2; number <= max; ++number)
		{
			if (number % prime == 0 && number != prime)
			{
				multiples.push_back(number);
			}
		}
	}
	return multiples;
}

vector<int> fill_reg_primes_v(int max)
{
	vector<int> primes;
	for (int i = 2, n = sqrt(static_cast<double>(max)); i <= n; ++i)
	{
		if (is_prime(i))
		{
			primes.push_back(i);
		}
	}
	return primes;
}

vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples, const int max)
{
	vector<int> eratosthenes_primes;
	bool is_multiple = false;
	for (int number = 2; number <= max; ++number)
	{
		for (int multiple : multiples)
		{
			if (multiple == number)
			{
				is_multiple = true;
				break;
			}
		}
		if (is_multiple)
		{
			continue;
		}
		eratosthenes_primes.push_back(number);
	}
	return eratosthenes_primes;
}

bool is_prime(int number)
{
	for (int i = 2; i < number; ++i)
	{
		if (number % i == 0)
		{
			return false;
		}
	}
	return true;
}

void print_primes(const vector<int>& eratosthenes_primes)
{
	for (const int prime : eratosthenes_primes)
	{
		cout << prime << "\n";
	}
}


I do know about ranged for loops, but for some reason I didn't originally get the idea to use them here.
Last edited on
I don't think you should give me the whole answer like that. Just tell me this: will it work after I've made the change you mentioned to fill_multiples_v()?

Sure, it's not an optimally way getting a whole solution of an exercise. I think the best way learning to programming is by having a skilled mentor on your side which you could ask if a problem arises. But if that is not feasable, the best way is, looking over good code examples. So I have here posted my solution. You could take that as a suggestion, and that I have posted the whole solution means not that you should code yours like my example. Feel free, looking at my suggestion only if you get sticked :-)

And no, at your code are some other errors then in fill_multiples_v().

For exercise 20: I would looping through the 'name'-vector for seaching the name, then taking its index number for getting the right score in the score-vector. Use a boolean flag, flagging if a match happend or not.

Ex. 21: Similar 20, traversing the score-vector in a for-loop for finding a matching number. Each time if such a match is found, remember the index-nr and print its name from the name-vector. Here helps also a flag for the right output.
Surely, with a map it would work better, I think. But I have still never worked with them until yet.

Feel free posting your exercise questions in the forum, I'm shure that they would also be very interesting for other students of c++.
Last edited on
Do you get why it's only printing 2 and 3 now? If so, please help me debug.

For exercises 20 and 21, what's confusing to me is how I'm going to look for a value that isn't there. I mean, if it's something the user JUST entered and the program doesn't allow for duplicate names, how am I going to search through the std::vectors for those elements? Or since the user had just entered it, I could just look at std::vector element v.size() - 1?

Edit: I got the Eratosthenes Primes one to work. But I don't get why the fill_eratosthenes_primes_v() function has to be like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> fill_eratosthenes_primes_v(const vector<int>& multiples, const int max)
{
	vector<int> eratosthenes_primes;
	for (int i = 2; i <= max; ++i)
	{
		bool is_multiple = false;
		for (int multiple : multiples)
		{
			if (multiple == i)
			{
				is_multiple = true;
				break;
			}
		}
		if (is_multiple) 
		{ 
			continue; 
		}
		eratosthenes_primes.push_back(i);
	}
	return eratosthenes_primes;
}


I tried putting the flag above the loops, but that made the program only print 2 and 3. And taking out the check for the flag makes it print all numbers, whether they're prime or composite. I don't get it. So I was just missing that flag in there?
Last edited on
Seem you haven't a method for good debugging. I for my self use the 'iterative' method, that's also been used by the rocket scientist Werner von Braun and many others.
Making extensive tests. First I test the the basic methods for getting them work correcly, and then I test for how they interact together. I make a control flow chart if its complicated, for better visualising. And then I trace the execution flow from start to end, compare the variables content for correctnes. I extensive use 'cout/cerr' for inspecting variables, test whether jumps happend in brunches and such. When I recognise that a funcion don't work correctly, I make at first sure that its input is correct, and than I check its output. Then I observe via cin/cerr its data of the execution flow to detect the error.
For your prime-example I suggest that you test in this order:
get_max_value()
print_primes()
is_prime()
fill_reg_primes()
fill_multiples()
fill_erastothenes_primes

Ex. 20-21: I don't see what there is a problem for you. The names are in a vector<string> and you can just iterate over it for checking if a same name is already there. Don't you know how traversing a vector or an array?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Here you can check if a entered name is a duplicate:
bool is_duplicate( const vector<string>& names_vec, const string& name_input)
{
     for( string name : names_vec) {
        if (name == name_input) {
            return true;
        }
    }
    return false;
}

// This returns all names which have a specivic score
vector<string> have_same_score(
          const int score
        , const vector<string>& names_vec
        , const vector<int> score_vec
) {
    vector<string> same_score_vec;

    for ( int i = 0; i < score_vec.size(); ++ i) {
        if ( score == score_vec[i] ) {
            same_score_vec.push_back( names_vec[i] )
        }
    }
    return same_score_vec;
}
I already check for if a name has already been entered once. I tested it and saw that it works correctly. What I'm asking is if I have to remove the code that makes the program exit with an error message if it detects a repeated name, since otherwise I wouldn't be able to search my vectors for the names or scores because they wouldn't have been entered yet.

So I guess I'll have to first tell the program to print out a message saying that the roster has been filled and that the user may now try to input scores and names to search the database (since the user shouldn't need to care how we're storing the data - they don't need to know that it's in vectors, and they shouldn't care) for a score to get the corresponding name or to input a name to get the corresponding score.
I think it's a good idea having nevertheless a (seperate invocable) function that does testing for name duplicates. Maybe it could be that you implement a reading-in from a file or such. And if a name duplicate is detected, then are still other options then exiting the program with an error. For example you could delete those names from your data base, or add a codicil to some of them.
You should been taking care for that a user don't input a duplicate. I he/she does it anyway, then you could print a message that the user must take another name.

"I got the Eratosthenes Primes one to work. But I don't get why the fill_eratosthenes_primes_v() function has to be like this..."
Sorry, here I've made an error. That's the price for re-editing working code and forgetting to test :-)
Wouldn't that be bad (for the names and scores one)? If we delete them, the user wouldn't be able to get the correct output with the corresponding name or score for their input. They'd only see "Name not found" or "Score not found" instead. I've taken out the check for duplicates and am asking for input after the vectors have been filled up.

But yeah, thanks for the help.
Topic archived. No new replies allowed.