sieve's Prime numbers
I have a problem that I am frustrated with. I have to allocate an array of size 1000, with all values set to 1.
The values in this array are used to determine if a number is prime or not, non prime numbers, at the end of the algoritm, will have the corresponding value set to 0. I then need to print out all prime numbers to the screen.
My teacher states no modulus operator is to be used!!!!!
I have been staring at my compiler for hours trying to work this. This has me lost. Any help would be appreciated.
#include <iostream>
#include <iomanip>
#include <math.h>
int main()
{
int Prime_Numbers_Array[1000];
int Array_Counter = 0;
// *****************************
// ** Initialize Array **
// *****************************
for (int Array_Counter = 0; Array_Counter < 1000; Array_Counter++)
{
Prime_Numbers_Array [Array_Counter] = 1;
}
for (int Array_Counter = 2; Array_Counter < 999; Array_Counter ++)
{
if Prime_Numbers_Array == 1
{
}
The values in this array are used to determine if a number is prime or not, non prime numbers, at the end of the algoritm, will have the corresponding value set to 0. I then need to print out all prime numbers to the screen.
My teacher states no modulus operator is to be used!!!!!
I have been staring at my compiler for hours trying to work this. This has me lost. Any help would be appreciated.
#include <iostream>
#include <iomanip>
#include <math.h>
int main()
{
int Prime_Numbers_Array[1000];
int Array_Counter = 0;
// *****************************
// ** Initialize Array **
// *****************************
for (int Array_Counter = 0; Array_Counter < 1000; Array_Counter++)
{
Prime_Numbers_Array [Array_Counter] = 1;
}
for (int Array_Counter = 2; Array_Counter < 999; Array_Counter ++)
{
if Prime_Numbers_Array == 1
{
}
Sieve of Erathosthenes.
To compute all of the prime numbers in the range 1 ... N, begin with an array of N booleans
with each boolean set to true. (Let us assume here that arrays are 1-based -- we know in
C/C++ they are not, so take care).
Now run a loop L from 2 to N. If the Lth index is set to true, then for all indices I = L*k, k>1,
set the Ith index to false.
At the end of the loop, run another loop Z from 1 to N. If the Zth index is set to true, then Z
is prime.
To compute all of the prime numbers in the range 1 ... N, begin with an array of N booleans
with each boolean set to true. (Let us assume here that arrays are 1-based -- we know in
C/C++ they are not, so take care).
Now run a loop L from 2 to N. If the Lth index is set to true, then for all indices I = L*k, k>1,
set the Ith index to false.
At the end of the loop, run another loop Z from 1 to N. If the Zth index is set to true, then Z
is prime.
So this is what I have for psuedocode. Does this make any sense?
1) allocate an array of size 1000, with all values set to 1. non prime numbers, at the end of the algoritm, will have the corresponding value set to 0.
2) Do the following loop:
for each number from 2 to 999 do
if (primeIndicators[number] is equal to 1)
for all multiple of number between 2 * number and 999
set primeIndicators[mulitiple of number] to 0
end for
end if
end for
3) print out the results:
for each number from 2 to 999 do
if (primeIndicators[number] is equal to 1)
print number
end if
end for
1) allocate an array of size 1000, with all values set to 1. non prime numbers, at the end of the algoritm, will have the corresponding value set to 0.
2) Do the following loop:
for each number from 2 to 999 do
if (primeIndicators[number] is equal to 1)
for all multiple of number between 2 * number and 999
set primeIndicators[mulitiple of number] to 0
end for
end if
end for
3) print out the results:
for each number from 2 to 999 do
if (primeIndicators[number] is equal to 1)
print number
end if
end for
jsmith - I am running into a problem with my program. It compiles but is not printing out Prime numbers 1 -1000. Can you look at it and give me a hint or two please?
/ ******************************************
// * Decalre & Initialize array elements to 1.
// ******************************************
int prime_number_array[1000];
int arraysize = 1000;
int i = 0;
int multiple_of_number;
for(i = 0; i<arraysize; i++) {
prime_number_array[i] = 1;
}
// ******************************************
// * End of initialization *
// ******************************************
// outside loop
for (i = 2; i < arraysize; i++)
{
if (prime_number_array[i]==1)
{
for (multiple_of_number = i+i; multiple_of_number < arraysize;
multiple_of_number = multiple_of_number + i)
{
prime_number_array[multiple_of_number] = 0 ;
}
}
}
for (i = 2; i < arraysize; i++) {
if (prime_number_array[i] = 1) {
cout << "The prime numbers of 1 - 1000 is:" << i << endl;
}
}
return 0;
}
/ ******************************************
// * Decalre & Initialize array elements to 1.
// ******************************************
int prime_number_array[1000];
int arraysize = 1000;
int i = 0;
int multiple_of_number;
for(i = 0; i<arraysize; i++) {
prime_number_array[i] = 1;
}
// ******************************************
// * End of initialization *
// ******************************************
// outside loop
for (i = 2; i < arraysize; i++)
{
if (prime_number_array[i]==1)
{
for (multiple_of_number = i+i; multiple_of_number < arraysize;
multiple_of_number = multiple_of_number + i)
{
prime_number_array[multiple_of_number] = 0 ;
}
}
}
for (i = 2; i < arraysize; i++) {
if (prime_number_array[i] = 1) {
cout << "The prime numbers of 1 - 1000 is:" << i << endl;
}
}
return 0;
}
Hi jsmith - just wanted to say thanks for the help. I felt like a million bucks when that program compiled and spit out all prime numbers.
Thanks again.
M.
Thanks again.
M.
Topic archived. No new replies allowed.