-
Prime Numbers
Prime Numbers 2 - 1000
Code:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
int main()
{
int array_size = 1000;
bool num[ array_size ];
for ( int a = 2; a < array_size; a++ ) // Set all elements to 1
{
num[ a ] = 1;
}
for ( int b = 2; b < array_size / 2; b++ )
{
if ( num[ b ] == 1 )
{
for ( int c = b; c < array_size; c + b )
{
num[ c ] = 0;
}
}
}
for ( int d = 2; d < array_size; d++ )
{
if ( num[ d ] == 1 )
{
cout << d << endl;
}
}
cin.get();
return 0;
}
No output.
Maybe the fact that it's 2 am whenever I try to do a question in the book doesn't help.
-
Code:
for ( int b = 2; b < array_size / 2; b++ )
{
if ( num[ b ] == 1 )
{
for ( int c = b; c < array_size; c + b ) //Does not change c
{
num[ c ] = 0;
}
}
}
My other guess is that this will try to set the whole array to false.
-
EDIT:
Code:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iomanip>
using std::setw;
int main()
{
int array_size =1000;
bool num[ array_size ];
int counter = 0;
for ( int a = 2; a < array_size; a++ ) // Set all elements to 1
{
num[ a ] = 1;
}
num[ 2 ] = 0;
for ( int b = 2; b < array_size / 2; b++ ) // Multiply all numbers from 1 to 500
{
if ( num[ b ] == 0 )
{
for ( int c = b; c < array_size; c += b ) // Eliminate multiples
{
num[ c ] = 0;
}
}
}
for ( int d = 2; d < array_size; d++ ) // Display
{
if ( num[ d ] == 1 )
{
cout << setw( 5 ) << d;
if ( counter % 10 == 1 )
cout << endl;
counter++;
}
}
cin.get();
return 0;
}
Nevermind, I got it right I just have some formatting issues.
Edit:
1 error: 999 comes out as prime!
In my output, why are the first 2 numbers alone? (The rest is fine)
Code:
5 7
7 9 11 13 ...... etc
-
> why are the first 2 numbers alone?
Either the start value for counter is wrong, or you're testing the wrong result.
-
The formating looks like this, because the first time you print the newline, counter is 1 (1%10=1).
The sieve itself as it is finds odd numbers - not primes at all.
Firstly you might use the keywords true and false (instead of 1 and 0) for the num array. Then decide what they stand for. It seems the value true (after the sieve) indicates that it is a prime.
Don't mark 2 as a non-prime (0).
In the loop, if you find a prime (that hasn't been marked as non-prime this far), mark all the values starting from (b+b) as non-primes (but not the number itself!).
b*b should also be a good starting value for marking non-primes, e.g for 3 you won't need to start marking non-primes at 6 which is already marked, but at 9 = 3*3. Similarly for 5, 10 is already marked as 2*5, 15 as 3*5 and 20 as 2*2*5 - hence 25 is the first number to mark.
-
Should be
Code:
const int array_size = 1000;
as standard C++ doesn't allow variable-length arrays.
-
Oh crap your right, its just odd numbers. I made a typo with true/false. My original output was prime numbers from 503 to 997:
Code:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iomanip>
using std::setw;
int main()
{
const int array_size = 1000;
bool num[ array_size ];
int counter = 0;
for ( int a = 2; a < array_size; a++ ) // Set all elements to 1
{
num[ a ] = true;
}
for ( int b = 2; b < array_size / 2; b++ ) // Multiply all numbers from 2 to half array size
{
if ( num[ b ] == true )
{
for ( int c = b; c < array_size; c += b ) // Eliminate multiples
{
num[ c ] = false;
}
}
}
for ( int d = 2; d < array_size; d++ ) // Display
{
if ( num[ d ] == true )
{
cout << setw( 5 ) << d;
if ( counter % 10 == 1 )
cout << endl << endl;
counter++;
}
}
cin.get();
return 0;
}
anon i'm not sure what your saying
Edit: no second condition
-
What I meant to say was this:
Code:
for ( int b = 2; b < (array_size / 2) + 1; b++ ) // Multiply all numbers from 2 to half array size
{
if ( num[ b ] == true /*|| b == 2*/) //why second condition??
{
for ( int c = b*b; c < array_size; c += b ) // Eliminate multiples
{
num[ c ] = false;
}
}
}
What happens in your code is that when you get to 2, you first mark b == c == 2 as non-prime, although the first non-prime to sieve out is 2*2 == 4. Similarly, when you get to 3, you mark it as non-prime, although the first non-prime to sieve out, again, is 3*3 == 9 (because you have already sieved out 6 == 2*3), etc.
It displayed anything at all because of the loop condition of the outer loop, meaning, the destruction would last only for the first half of the array...
-
Oh I get it now! Thanks for not giving up on me :) Hmm that b * b was a good idea, although I'm not exactly sure why it never skips a number.
Code:
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iomanip>
using std::setw;
int main()
{
const int array_size = 1000;
bool num[ array_size ];
int counter = 2;
for ( int a = 2; a < array_size; a++ ) // Set all elements to 1
{
num[ a ] = true;
}
for ( int b = 2; b < (array_size / 2) ; b++ ) // Multiply all numbers from 2 to half array size
{
if ( num[ b ] == true )
{
for ( int c = b + b; c < array_size; c += b ) // Eliminate multiples
{
num[ c ] = false;
}
}
}
num[ 2 ] = true;
for ( int d = 2; d < array_size; d++ ) // Display
{
if ( num[ d ] == true )
{
cout << setw( 5 ) << d;
if ( counter % 10 == 1 )
cout << endl << endl;
counter++;
}
}
cin.get();
return 0;
}
And by setting counter to 2, how come I still get 10 in each row? AGH!
-
Also, if I wanted to increase the number to a very high one, how would I get it to display all the numbers, instead of only the last few?