Printing prime numbers 1-100

Recommended Posts

Theo Berlin    121

Hi, I'm reading Bjorne Stroustrups "Programming Principles and Practice Using C++". Right now I'm doing exercises and I'm supposed to print the prime numbers from one to hundred. I've seen a few other C++ programs that does this, but they use modulo, which I'm not supposed to have learned yet, so I have to come up with a solution without that. Also, I must use a vector to store the prime numbers.

My code is a big mess, and whenever I start it up I get memory problems and the app crashes. Any ideas on how to solve this would be very much appreciated : )

Almost forgot: the program has to use the "Sieve of Eratosthenes" method. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

#include "../../std_lib_facilities.h"
int main()
{
vector<int>primes;
for (int i=0;i < 100; ++i){
primes.push_back(i+1);}
vector <int> not_primes;

for (int p = 2; p < 100;)
for (int not_prime = 2; not_prime < 100;)
{
not_prime += p*2;
not_primes.push_back(not_prime);
if (not_prime == 100){
for (int i = 0; i < 99; i++)
{
if (primes [i+2] = not_primes[i])
primes [i+2] = 0;
}
if (primes[p+1] != 0)
++p;
else if (primes[p+1] == 0){
for (int v = 1; primes[p+v] != 0;)
p += v;
}
}

for (int i = 0; i < 100; ++i)
{
//if (primes[i] =! 0)
cout << primes[i] << endl;
cout << not_primes[i] << endl;
}
}
keep_window_open();
}


Share on other sites
SiCrane    11839

It looks like your crash problem is the output loop at the end. primes and not_primes won't have 100 elements each. You should loop over the number of elements they actually have rather than going from 0 to 99. Either use std::vector<>::size() to get the number of elements in each vector or use iterators to loop over each vector.

Share on other sites

if (primes [i+2] = not_primes[i])
primes [i+2] = 0;

You probably intended to do a comparison (==) instead of assignment (=) here.

Share on other sites
alvaro    21246

I didn't quite follow all of your code, but  it seems like a very odd implementation of Eratosthenes's sieve. The primary data structure you need is an array of booleans indicating whether a number is a plausible prime or not. Initially, all numbers 2 and up are plausible primes.

  std::vector<bool> plausible_prime(100, true);
plausible_prime[0] = false;
plausible_prime[1] = false;

Then you find the first boolean set to true in that table, determine its index is prime (you can print it, or push_back it to a vector or whatever), set all its multiples to false (you can start at the square of the prime, as an optimization) and do it again, until you get to the end of the table.

Share on other sites
Theo Berlin    121

I didn't quite follow all of your code, but  it seems like a very odd implementation of Eratosthenes's sieve. The primary data structure you need is an array of booleans indicating whether a number is a plausible prime or not. Initially, all numbers 2 and up are plausible primes.

  std::vector<bool> plausible_prime(100, true);
plausible_prime[0] = false;
plausible_prime[1] = false;

Then you find the first boolean set to true in that table, determine its index is prime (you can print it, or push_back it to a vector or whatever), set all its multiples to false (you can start at the square of the prime, as an optimization) and do it again, until you get to the end of the table.

I like your bool solution, and I've changed my code quite a bit. However, the Visual Studio's giving me an error and it can't build it. "error C2440: 'return' : cannot convert from 'std::_Vb_reference<_Alloc>' to 'bool &'".

#include "../../std_lib_facilities.h"
int main()
{
vector<bool>plausible_prime(100, true);
plausible_prime[0] = false;
plausible_prime[1] = false;

for (int p = 2; p < 100;)
for (int not_prime = 2; not_prime < 100;)
{
not_prime += p*2;
plausible_prime[not_prime] = false;
if (not_prime >= 100){
if (plausible_prime[p+1] != false)
++p;
else if (plausible_prime[p+1] == true){
for (int v = 1; plausible_prime[p+v] == false;)
p += v;
}
}
}

for (size_t i = 0; i < plausible_prime.size(); ++i)
{
if (plausible_prime[i] =! false)
cout << plausible_prime[i] << endl;
}
keep_window_open();
}


Share on other sites
alvaro    21246

I don't know what your error message is saying, but at least you have one obvious mistake: =! and != are not the same thing.

I still don't understand how your program is supposed to work, but it seems confused. The way you search for the next prime is really convoluted, and (not surprisingly) wrong. At the end you print a bunch of "1"s, which is probably not what you want.

Share on other sites

I'd suggest going through the algorithm by hand on a piece of paper (maybe not for all numbers from 1 to 100 though) before sitting down at the computer and typing. You'll end up with an array of numbers some of which are crossed out.

Share on other sites
Theo Berlin    121

At the end you print a bunch of "1"s, which is probably not what you want.

I'm trying to print all the prime (true) numbers with

	for (size_t i = 0; i < plausible_prime.size(); ++i)
{
if (plausible_prime[i] == true)
cout << plausible_prime[i] << endl;
}


It's always worked for me, but what am I doing wrong this time?

Share on other sites

Try printing out i + 1 instead ;) You are just printing out true (or 1, depends on the implementation of outputting bools) however many times that you think there is a prime in the set.

You need to print out i + 1 since you start counting at 0.

EDIT: I don't think what you are doing before that is correct though, but that should help you debug it.

Share on other sites
Bacterius    13165

At the end you print a bunch of "1"s, which is probably not what you want.

I'm trying to print all the prime (true) numbers with

	for (size_t i = 0; i < plausible_prime.size(); ++i)
{
if (plausible_prime[i] == true)
cout << plausible_prime[i] << endl;
}


It's always worked for me, but what am I doing wrong this time?

Read the code here - you are iterating through the list of numbers, and if it's a plausible prime... you print the fact that it is. Your code prints plausible_prime[i] if and only if plausible_prime[i] is true. So you're always printing the same thing.

You probably wanted something along the lines of "for every number, if it's a plausible prime, print it", that is:

for (size_t i = 0; i < plausible_prime.size(); ++i)
{
if (plausible_prime[i] == true)
cout << i << " is prime." << endl;
}


Or something like that. It worked before because before, your vector was a collection of integers which you could just print. But now it's a list of booleans which all implicitly correspond to a given integer, so you need to account for that when printing out your results

EDIT: also offset as needed, as noted by Paradigm Shifter above, if you start your boolean list at 1 then use i + 1 since the array starts at zero by convention.

Edited by Bacterius

Share on other sites

It looks like they are mapping 0 to 1, etc.

I'm not sure about the code which sets the first 2 numbers as not prime though, that would suggest 1 and 2 are not prime. I agree that 1 is not prime. I'm sure that 2 is prime though ;)

You could always use 101 length vectors and just ignore element 0, you would be less likely to make a silly error then.

I'm still advocating running through the algorithm on a piece of paper before starting coding (looks like it is a bit late for that now though)...

Share on other sites

Oh, editing is broken for me now as well.

I was going to suggest once you get it working with a 101 element array rewrite it to use only a 100 element array and map 0 to 1, etc. But do that after you have a working implementation to compare the output against. Later on you could also be clever and not store plausible_prime entries for even numbers (output 2 as the first prime and then no other even numbers after that are prime so you don't really need to remember whether they were prime or not).

EDIT: Test edit...

I've been having bugs on this site this evening, but it isn't letting me start a thread in Comments & Suggestions about them, it just looks like it is loading a page and then never finishes (or it is taking far too long to generate the new post form).

Share on other sites
Theo Berlin    121

Writing it down on paper was a great idea.

Perhaps the algorithm should be something more like this?

not_prime = p * p;
plausible_prime[not_prime] = false;
while (not_prime <= 100)
{
not_prime += p;
plausible_prime[not_prime] = false;
}


Share on other sites

Try it out.

If you type

primes <= 100

into wolframalpha you get this:

2  |  3  |  5  |  7  |  11  |  13  |  17  |  19  |  23  |  29  |  31  |  37  |  41  |  43  |  47  |
53  |  59  |  61  |  67  |  71  |  73  |  79  |  83  |  89  |  97   (25  primes)

Share on other sites
Theo Berlin    121

Changed the code a bit and checked some stuff. I think the algorithm looks good now, but visual studio still gives me: "error C2440: 'return' : cannot convert from 'std::_Vb_reference<_Alloc>' to 'bool &'". Whenever I try to debug it tells me there were build errors and if I ignore it the app crashes and it says something like "Range_error at memory location...".

#include "../../std_lib_facilities.h"
int main()
{
vector<bool>plausible_prime(100, true);
plausible_prime[0] = false;
plausible_prime[1] = false;

for (int p = 2; p < 100; ++p)
for (int not_prime = 2; not_prime < 100;)
{
not_prime += p * p;
plausible_prime[not_prime] = false;
while (not_prime <= 100)
{
not_prime += p;
plausible_prime[not_prime] = false;

if (not_prime >= 100){
if (plausible_prime[p+1] != false)
++p;
else if (plausible_prime[p+1] == true){
for (int v = 1; plausible_prime[p+v] == false;)
p += v;
}
}
}
}

for (size_t i = 0; i < plausible_prime.size(); ++i)
{
if (plausible_prime[i] == true)
cout << i+1 << " is prime." << endl;
}
keep_window_open();
}


Also, it's still printing 1 (repeatedly).

Thanks a lot for the help you've given me! I'm going to sleep for now.

Edited by Theo Berlin

Share on other sites
Bacterius    13165

Don't ignore build errors. If there's a build error and you ignore it then VS will simply run the last working version (the incorrect one which prints all 1's). Which I consider to be absolutely retarded behaviour but anyway. You need to fix that error before it'll run. I'm not too sure what the problem is but it seems to be coming from the vector<bool> implementation. It works fine here on gcc (as far as compilation goes - the algorithm is still not quite correct) so it looks like a MSVC quirk (your compiler). Try this instead to initialize the vector and see if it makes a difference:

vector<bool> plausible_prime(100);

plausible_prime[0] = false;
plausible_prime[1] = false;
for (int i = 2; i < plausible_prime.size(); ++i) plausible_prime[i] = true;


Also, the "not_prime = p * p" line doesn't look quite right. You need to tick off multiples of whatever prime you found, so you should start from your prime P and then mark 2 * P, 3 * P, ... as non-prime until you reach 100.

Share on other sites

You can start at p*p because other multiples of p will have already been crossed off the list.

e.g. when you discover 5 is a prime, 2*5, 3*5, 4*5 will already have gone because you crossed off all multiples of 2, 3 and 4 in an earlier stage.

It looks like you are accessing elements outside the array range to me. These lines look potentially dodgy

if (plausible_prime[p+1] != false)
++p;
else if (plausible_prime[p+1] == true){
for (int v = 1; plausible_prime[p+v] == false;)
p += v;

Also, which line is the error about the vector<bool> occuring? The implementation of vector<bool> can be a bit weird, since the bools are packed into bitfields, try changing it to vector<int> instead, for now at least.

Share on other sites
alvaro    21246
The way I imagined the code, indices are not offset by 1: That's asking for trouble! I created a vector with 100 entries because the statement of the problem says "from one to hundred", which in full C++ spirit means {1,2,3,...,99}.

#include <iostream>
#include <vector>

long const N = 100;

int main() {
std::vector<bool> v(N, true);
v[0] = v[1] = false;

std::vector<long> primes;

for (long p=0; p<N; ++p) {
if (v[p]) {
primes.push_back(p);
for (long i=p*p; i<N; i+=p)
v[i] = false;
}
}

for (long p : primes)
std::cout << p << '\n';
}
Edited by Álvaro

Share on other sites

I think the idea is for the OP to do the exercise and learn some stuff, rather than just be given the answer ;)

In your solution though (so indices correspond directly to the numbers):

I wouldn't bother with a second vector to hold the primes, I'd just loop through v (terrible variable name though) and output i if v[i] is true. You can also do the output in the if(v[p]) loop, so you don't need to loop through the vector again.

EDIT: Although I didn't see this bit in the OP

"Also, I must use a vector to store the prime numbers."

so perhaps an extra vector is required just to hold the primes after all.

Share on other sites
alvaro    21246

I think the idea is for the OP to do the exercise and learn some stuff, rather than just be given the answer ;)

Yes. He's free to ignore my code if he wants. But I think he was a little bit too lost. I tried to write the code in the most straight-forward way I could.

EDIT: Although I didn't see this bit in the OP

"Also, I must use a vector to store the prime numbers."

so perhaps an extra vector is required just to hold the primes after all.

Yes, that's the only reason I stored them in a vector.

Share on other sites

OK then. I'm just glad you didn't do a solution involving magic octal numbers!

I thought the OP looked a bit lost too, which is why I said to do it on paper first before starting coding ;)

Share on other sites
Theo Berlin    121

I'm trying to learn from your code, Alvaro. However, what does this mean?

    if (v[p])

Does it mean "if element p exists"? Or does it mean "if element p is true"?

I agree with you, Paradigm, I shouldn't just be given an answer, but since I don't have a teacher and no homework, it's my responsibility to make sure I learn something. And it kinda felt like I was lost (as alvaro mentioned). So in this case, giving me a code isn't a shortcut, it's a source which I can use to learn from. The only downside is that it's not as easy to remember something you read "just like that".

Share on other sites
Theo Berlin    121

Also, which line is the error about the vector<bool> occuring? The implementation of vector<bool> can be a bit weird, since the bools are packed into bitfields, try changing it to vector<int> instead, for now at least.

The annoying thing is that visual studio says "line 88" in the std_lib_facilities.h file, not in the actual source file. I tried running Alvaro's solution wth SL and it gives me the exact same error.

Share on other sites

I'm trying to learn from your code, Alvaro. However, what does this mean?

    if (v[p])

Does it mean "if element p exists"? Or does it mean "if element p is true"?

it means "if element p is true"?. the if statement will evaluate the condition, if it's true it will execute the first branch, the second branch otherwise, so saying "if (boolean==true)" is a bit redundant and means exactly the same thing than "if (boolean)"

The same goes with numerical values : saying "if (integer!=0)" if exactly the same than "if (integer)", since for numerical values the if statement checks if it's not zero.

(In fact this is the same behaviour for any type of value : first branch if not zero, second branch otherwise)

Edited by Tournicoti

Share on other sites
Theo Berlin    121

Okay, thanks!