Sieve of Eratosthenes finding every number to be prime?

[jambo0606]

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.

[Smac89]

jambo0606 wrote:

In addition, is there anyway to make the array A of a user inputted size?

bool* sieve;
unsigned size;
std::cout << "Enter the number\n";
cin >> size;
sieve = new bool[size+1];

[naraku9333]

 for(int i = 2; i < sqrt(n); i++)
{
if (A[i] == true)
{
for (int j = i * i; i < n; ++i)
{
A[j] = false;
}
}
}

You initialize n to 0 but never change it so this loop never runs.

[cire]

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.

#include <vector>
// ...
    cin >> n ;
    std::vector<bool> A(n, true) ;  // vector of n bool values all set to true.
// ...  

[jambo0606]

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!

Here's the working code if anyone is interested:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	bool* A;
	unsigned n;
	cout << "Enter a number: " << endl;
	cin >> n;
	n += 1;
	A = new bool[n];
	
	for(int i = 2; i < n; i++)
		A[i] = true;

	for(int i = 2; i < sqrt(n); i++)
	{
		if (A[i] == true)
		{
			for (int j = i * i; j < n; j+= i)
			{
				A[j] = false;
			}
		}
	}

	cout << "The prime numbers below " << (n-1) << " are: " << endl;
	
	for(int i = 1; i <= n; i++)
	{
		if (A[i] == true)
		{
			cout << i << endl;
		}
	}
	
	return 0;

}

Thanks again. James.

[ar2007]

I think this is ok.

#include <iostream>
#include <cmath>

using namespace 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.

[ar2007]

trange .. when I put my post your solution was not there.!

[jambo0606]

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.

Any ideas on how to fix this? Thanks.

[ar2007]

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

[jambo0606]

What variable is causing me an issue? n? As I've changed that to an unsigned int64 and the program still does not work with 600851475143.

[Chervil]

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.

[vlad from moscow]

The compiler is unable to place such a big array as

bool A[600851475143];

in the stack.

Either make it with the static storage duration or allocate it dynamically.