QUOTE(sanjozen @ 23 Nov, 2007 - 04:35 AM)
I'm supposed to use the "Sieve of Eratosthenes" algorithm to generate prime numbers without using modulus in the innermost loop.My code below works perfect but I cannot figure out how NOT to use modulus.
Any hints???
CODE
//
// primeNumGenerator.cpp
//
// Samuel Gathairu
// 11/18/07
// Assignment10
// Program uses the "Sieve of Eratosthenes" algorithm to calculate and
// print all prime numbers less than or equal to 20.
//
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
int main()
{
char outFilename[30];
bool bArray[21];
int i, j;
int count = 0;
int numCols = 3;
cout << "This program will generate all prime numbers up to 20 \n";
cout << "Enter the name of the output file : ";
cin >> outFilename;
for( i = 2; i <= 20; i++ )
{
bArray[i] = true;
for( j = 2; j <= i / 2; j++ )
{
if( bArray[i] == true )
{
for( j = 2; j <= i / 2; j++ )
{
if( (i % j) == 0 ) //-> NO MODULUS WHATSOEVER!!!!
{
bArray[i] = false;
}
}
}
}
}
ofstream fout(outFilename);
fout << "The prime numbers between 0 and 20 are:\n";
for( i = 2; i <= 20; i++ )
{
if( bArray[i] == true )
{
if( (count % numCols) == 0 )
{
fout << "\n";
}
fout << setw(6) << i << " ";
count++;
}
}
fout << endl;
return 0;
}
seems like a lot of this sieve of erathosthenes is needed. third time i encountered this thing.
anyway your code on initializing the array to true should be separated from the rest of the sieving out nonprimes.
what you actually did was combine both initializing and sieving out which would SURELY lead to errors. also another point here is the fact that you are halving an int which would skip some elements of your array
to solve this initialize all the elements of your array to 1 separate from the other instructions. then starting from 2, get all multiple of the index and set it to false. to do this:
[code]for(int i=2; i < array_size; i++) {
if (array[i] == true) {
for(int j = i + i; j < array_size; j += i) {
array[j] = false;
}
}
}[code]
that should eliminate the need for the modulo.
what the code does is step through the array starting from index 2 and checking if the corresponding array element is true. if true, it sets another index to next multiple of the first index and adding the value of the first index to the second index while setting elements of the array to false
Mod Edit: Please use code tags:
23 Nov, 2007 - 03:35 AM
| 