I've been trying to make a Sieve of Eratosthenes following the pseudocode off Wikipedia, yet something is going wrong with the execution and it's saying every number is prime? For now I'm testing it with 100, trying to find the prime numbers below 100, yet it's saying that every number is prime and I, being fairly new to this, have no idea why.
Here is the psuedocode:
Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., √n :
if A[i] is true:
for j = i2, i2+i, i2+2i, ..., n:
A[j] := false
Now all i such that A[i] is true are prime.
Here is the code I'm using:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n = 0;
bool A[101];
for(int i = 2; i < 101; i++)
A[i] = true;
for(int i = 2; i < sqrt(n); i++)
{
if (A[i] == true)
{
for (int j = i * i; i < n; ++i)
{
A[j] = false;
}
}
}
for(int i = 1; i <= n; i++)
{
if (A[i] == true)
cout << i << endl;
}
return 0;
}
In addition, is there anyway to make the array A of a user inputted size? I tried:
cin >> n;
bool A[n];
but that doesn't seem to work.
Any help would be great, as I've said I'm fairly new to this. Thanks in advance, James.
I don't know how the code you posted could result in every number being prime as none of the for loops are entered into since n is given the value 0 initially and is never changed.
In addition, is there anyway to make the array A of a user inputted size? I tried
Use a vector instead.
1 2 3 4 5
#include <vector>
// ...
cin >> n ;
std::vector<bool> A(n, true) ; // vector of n bool values all set to true.
// ...
Thank you everyone that replied, I'm so stupid for missing that! I forgot to set the value for n and I also used the wrong variable in a loop. It's all part of the learning process!
#include <iostream>
#include <cmath>
usingnamespace std;
int main()
{
int n = 30;
bool A[100];
for(int i = 2; i < n; i++)
A[i] = true;
for(int i = 2; i <= sqrt(n); i++)
for (int m=2; m<=n/i; m++)
{
int j=m*i;
A[j] = false;
}
for(int i = 2; i <= n; i++)
{
if (A[i] == true)
cout << i << endl;
}
return 0;
}
there were small useless things and the problem is that you do not delete a number, if not calculate the multiples of that number. the Sieve of Eratosthenes is based primarily on the elimination of the MULTIPLES of prime numbers found.
Sorry, I don't know whether I should make a new post for this or if I should continue on this one. The code I posted above works for numbers like 100, however if I wanted to decompose a larger number, e.g. 600851475143, it would result in an error:
Unhandled exception at at 0x7530C41F in Project Euler.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x002BF8F4.
strange too ..
have you learned the dynamic memory management in 1 hour and then you do not recognize not even a limit of one type of variable??
strong
If you change n to a 64-bit int, then any variable used in an expression such as j < n should ideally be of the same type.
But if you are dealing with a number such as 600851475143 then using a sieve may not be the best approach, or at least there are alternative methods, some of which don't involve finding primes at all.