0

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

0

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.

  • Oh yes you're right! This works perfectly! Thank you! I see, memory arrays can't be dynamic... Do you have any suggestions on how to do to have a dynamic array? Using "storage"? But it would use a huge amount of gas I think. – Slevin Nov 27 '17 at 7:35
  • Yes, don't use storage unless you want to persist the data - way too expensive. You just have to work around the lack of dynamic sizing (we old-school coders are much more comfortable with it: C doesn't have dynamic arrays, for example). In this example, it depends what you want to do with the primes. I'd probably just use my first block of code and consider j to be the array size. – benjaminion Nov 27 '17 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.