How to remove "0" from array and readjust the size of the array?

Question

This function works but returns zeros when condition not met. For instance if limit is 10 it will return: 2, 3, 0, 5, 0, 7, 0, 0, 0, 0 But instead I want it to return: 2, 3, 5, 7. Also is there a way to do so without specifying the length of primeswithoutzeros ? I can't figure out how to solve the problem...

function sieveOfEratosthenes(uint256 limit) constant returns (uint256[] memory primeswithoutzeros){
    uint256[] memory primes = new uint256[](limit + 1);
    primeswithoutzeros = new uint256[](limit);
    for (uint256 i = 2; i < limit; i++){
        primes[i] = i;
    }
    i = 2;
    while(i**2 <= limit){
         if (primes[i] != 0){
            for (uint256 j = 2; j < limit; j++){
                if (primes[i] * j > limit){
                    break;
                }
                else {
                   delete primes[primes[i] * j];
                }
            }
         }
        i++;
    }
    for (i = 2; i <= limit; i++){
        if (primes[i] != 0){
            primeswithoutzeros[i - 2] = primes[i];
        }
    }
}

Thank you

Answer 1

If you just want the primes contiguous, then this works, but you get a bunch of zeros at the end:

function sieveOfEratosthenes(uint256 limit) constant returns (uint256[] memory primeswithoutzeros){
    uint256[] memory primes = new uint256[](limit + 1);
    primeswithoutzeros = new uint256[](limit);
    for (uint256 i = 2; i < limit; i++){
        primes[i] = i;
    }
    i = 2;
    while(i**2 <= limit){
        if (primes[i] != 0){
            for (uint256 j = 2; primes[i] * j <= limit; j++){
                delete primes[primes[i] * j];
            }
        }
        i++;
    }
    j = 0;
    for (i = 2; i <= limit; i++){
        if (primes[i] != 0){
            primeswithoutzeros[j] = primes[i];
            j++;
        }
    }
}

j is the number of primes resulting.

If you actually want a shorter array, then you can do something like this, but it's not very beautiful. You can probably improve it.

function sieveOfEratosthenes(uint256 limit) constant returns (uint256[] memory primeswithoutzeros){
    require(limit >= 2);
    uint256[] memory primes = new uint256[](limit + 1);
    for (uint256 i = 2; i < limit; i++){
        primes[i] = i;
    }
    i = 2;
    uint256 k = limit - 2;
    while(i**2 <= limit){
        if (primes[i] != 0){
            for (uint256 j = 2; primes[i] * j <= limit; j++){
                if (primes[primes[i] * j] != 0) {
                    delete primes[primes[i] * j];
                    k--;
                }
            }
        }
        i++;
    }
    j = 0;
    primeswithoutzeros = new uint256[](k);
    for (i = 2; i <= limit; i++){
        if (primes[i] != 0){
            primeswithoutzeros[j] = primes[i];
            j++;
        }
    }
}

In memory arrays cannot be dynamically sized, unfortunately.