Using 2D arrays to solve Sieve of Eratosthenes with C++

Question

I'm not really sure what's going wrong with my program here. It compiles without error but it won't even run the first function correctly. I have tried to ask some friends to help me out with this but they were of no help.

I am hoping someone could help me at least by showing me an error I have made but have not caught.

Header File (sieve.h):

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <vector>
using namespace std;

void findPrimeNumbers(int**, int);
void printPrimes(int**, int);

void findPrimeNumbers(int **arr, int n)
{
    for (int x = 2; x < n; x++){
       cout << " x is " << x;
        if (arr[0][x] == 1){
        int z = arr[1][x];
        cout << " z = " << z;
        for (int y = 2 * z; y < 40; y += z){
                cout << " y is " << y;
                arr[0][y] = 0;
            }
        }
    }
}

void printPrimes(int **arr, int n)
{
    for (int x = 0; x < n; x++){
        if (arr[0][x] == 1) 
            cout << arr[1][x] << " is a prime number" << endl;
    }
}

Main File (sieve.cpp):

#include "sieve.h"

using namespace std;

int main()
{
    int n=1;
    cout << "Please enter the maximum value:" << endl;
    cin >> n;
    vector<int> sir(n);
    cout << "You have selected the maximum size as:" << endl;
    cout << n << endl;
    //allocate the array
    int row = n;
    int col = n;
    int** arr = new int*[row];
    for(int i = 0; i < row; i++)
    {
        arr[i] = new int[col];
    }
    findPrimeNumbers(arr, n);
    printPrimes(arr, n);
    for (int j = 0; j < n; j++)
    {
        cout << " " << arr[0][j];
    }
    //deallocate the array
    for(int i = 0; i < row; i++)
    {
        delete[] arr[i];
        delete[] arr;
    }
    return 0;
}

Even the tiniest amount of help would be greatly appreciated!

I am trying to teach myself how to use dynamically created 2D arrays properly. It's something my professor never really taught me how to do correctly. — , Sep 24 '13 at 20:44
Sure - but how are you going to use a 2D array for a 1D algorithm such as this sieve ? — Paul R, Sep 24 '13 at 20:45
Leaving aside the need for 2d array, why are you reading the array values without ever initializing them? — Leeor, Sep 24 '13 at 20:48
I don't know how to. How can I declare the values of the array from 1 to the max size? — , Sep 24 '13 at 21:14

score 0 · Answer 1 · answered Sep 24 '13 at 20:44

0

You have one problem here:

//deallocate the array
for(int i = 0; i < row; i++)
{delete[] arr[i];
delete[] arr;}

You should not be deleting arr in the loop. Formatting the code properly would probably have alerted you to this mistake - it should be:

//deallocate the array
for(int i = 0; i < row; i++)
{
    delete[] arr[i];
}
delete[] arr;

Ideally though you should not even be using raw arrays like this - use std::vector instead.

answered Sep 24 '13 at 20:44

Paul R

208,748
37
389
560

Honestly, that is just a minor problem here, not the root cause of the main problem. – Doc Brown Sep 24 '13 at 20:46
@Doc: true, it's not the root cause, but it is a serious bug, and it also highlights the problem of badly formatted code (harder to spot simple errors). – Paul R Sep 24 '13 at 20:47
Don't know anything about that's why I was trying to use this. – Sep 24 '13 at 21:15
OK - if you're going to learn C++ properly then you really need to get to grips with C++ idioms and the standard container classes like `std::vector`, etc. This may seem challenging at first, but ultimately it's a lot easier and more robust than messing about with pointers. – Paul R Sep 24 '13 at 21:18
Sure - any good introductory book on C++. (You are working from a book, I hope ?) See [this question](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) for a comprehensive list. – Paul R Sep 24 '13 at 21:23
1

Yes, ok, I found the part that talks about Vectors. Reading it now. – Sep 24 '13 at 21:23

Benjamin Lindley · Answer 2 · 2013-09-24T21:09:56.330

int z = arr[1][x];

At the point this happens in the findPrimeNumbers function, arr[1][x] has not been initialized, which means you have undefined behavior when you try to read that value.

Besides that, what you're doing doesn't really make any sense, and doesn't seem to be an implementation of the Sieve of Eratosthenes. You don't need a 2 dimensional array, you need a 1 dimensional array of boolean values. When processing is complete, arr[N] should be true if N is a prime number, and false if it's not.

Using 2D arrays to solve Sieve of Eratosthenes with C++

2 Answers2