First of all, let me exaplain that I only really know python. I thought I would give c++ a try and since then (about two days ago), I have read a few tutorials and have made a guess number game. I thought I would be able to rewrite one of my python programs, a prime number generator into c++, I know I probably did it horribly wrong, but I really do appreciate all help. Heres the code:

``````#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
int counter = 3;
double sq = 0;
int i = 0;
int prime = 1;
cout << "2" << endl;

for(;;)
{
prime = 1;
sq = (sqrt(counter)) + 1;
for(i = 1; i <= sq; i++)
{
if(counter % 2L)
{
prime = 2;
break;
}
}
if(prime == 1)
{
cout << counter << endl;
counter += 2;
}
else if(prime == 2)
counter += 2;
}
}``````
3
Contributors
4
Replies
5
Views
10 Years
Discussion Span
Last Post by Matt Tacular

You seem to be making this program needlessly complicated.

Consider doing the following things:

• Nesting 2 loops inside each other
• The first loop goes (y) through all the numbers until x
• The second loop (z) goes from 2 to y-1
• Inside the second loop, check if y can be divided evenly by z.
• If false, the number is prime
• If true, number is not prime; break out of loop

Ok I got it to work identicle to it's python counterpart. However this one executes about 10 times faster it seems. I'm unsure about most of the stuff you said to consider doing, unsure what you mean by them.

Nesting 2 loops inside each other - how do I do that?

If false, the number is prime - I understand how to set it as false (ex. prime = false, or prime = true) but how do I declare a variable that will be used like that? I use that in the python version but in c++ it said the variable was undeclared and I couldn't figure out what to declare it as.

thanks.

``````#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
double sq = 0.0;
int i2 = 0;
int i = 0;
int prime = 1;
cout << "2" << endl;

for(i2 = 3; ;i2 = i2 + 2)
{
prime = 1;
sq = (sqrt(i2));
for(i = 3; i < sq; i = i + 2)
{
if((i2 % i) == 0)
{
prime = 2;
break;
}
}
if(prime == 1)
{
cout << i2 << endl;
}
}
system("PAUSE");
}``````

A very simple algorithm for your needs:

• Declare variables to hold the prime limit (the number till you want the prime numbers to be generated) and a flag which indicates whether a prime number was found or not (a boolean variable).

• Since while checking for primes we normally say that if a number is divisible by only 2 and itself then its a prime number. We can use a short cut here by considering that if a number is not divisible by any number between 2 and its square root, its a prime number.

• To achieve the above task, we would be needing two loops, one to generate all the numbers and the other for testing the numbers.

• Run the outer loop from 2 to the LIMIT and let the control variable (loop variable) be i.

• Run an inner loop with control variable j, where j starts from 2 and the loop runs till the square of i is less than or equal to j (short cut method)

• Inside the nested loops test whether i is completely divisible by j ( i % j = 0 ) .

• If the above condition is true, then we can conclude that the number is not prime. In this case, set the prime found flag to false and break out of the inner loop.

• After breaking out of the loop test whether we ducked out of the loop due to the condition failure or because of natural loop completion.

• If we broke out of the loop naturally, then the number i under consideration is prime. So print it.

• If we broke out of loop because of condition failure then the number "i" is not prime and so reset the flag.

• At the end of both the loops we would have a list of all the prime numbers.

Here is a sample:

``````#include <iostream>

int main ()
{
using namespace std ;

int limit = 0, prime_count = 0 ;
bool is_prime = true ;

cout << "Prime numbers till what? " ;
cin >> limit ;
getchar( ) ;

for( int i = 2; i < limit; ++i )
{
for( int j = 2; j * j <= i; ++j )
{
if ( i % j == 0 )
{
is_prime = false ;
break ;
}
}
if( is_prime )
{
++prime_count ;
cout << i << '\n' ;
}
else
{
is_prime = true ;
}
}

cout << "\nTotal of " << prime_count << " prime numbers were found." ;

getchar( ) ;
return 0 ;
}``````

but what's the point in checking if any even number is a prime? we already know it won't be, it will be divisible by 2. that's why the first loop started at three and went up by twos. and if we aren't checking if even numbers are primes, then why divide by even numbers? which is why the second loop also starts at 3 and goes up by twos. It was just the c++ programming i didn't understand. And I learned alot about it from your post, like how to declare a boolean variable, for which I am very greatful.

And I made it have no limit because I just wanted it to keep going until you exit it.

A also thank you for this

``getchar();``

because I would always use

``system("PAUSE");``

which would display that stupid "press any key to continue"

``for(int j = 2; j * j <= i; ++j)``

That's cool because it's easier than finding the square root first.

Thanks for all your help everyone.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.