Jump to content
  • Advertisement
Sign in to follow this  
Theo Berlin

Printing prime numbers 1-100

This topic is 1815 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
Share on other sites

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 this post


Link to post
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 this post


Link to post
Share on other sites

 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 this post


Link to post
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.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites


 



 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 if and only if plausible_prime 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 smile.png

 

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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!