Project Euler #10 - Attempting to Improve Efficiency of Bash Prime Sieve

Projects Personal Projects
1

Hello all,

First post on the forum! Nice to meet you :slight_smile:

I’m working through Project Euler problems, learning many languages in the process. One language that I have trouble with in general is Bash, because it’s really easy to write inefficient code relating to arithmetic operations.

So, this is the prompt of problem 10 on Project Euler:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

And here is my Bash code which solves it. Unfortunately, I haven’t even waited long enough for this code to complete, it’s too slow! I’m thinking that the inefficiencies arise while building the array, which is done in the first for-loop.

# initialize variables
size=2000000
gross=2

# initialize array
prime=()
for (( i=0; i<size; i++ )); do
    (( i % 2 == 1)) && prime+=(1) || prime+=(0);
done

# one is not prime, two is
prime[1]=0;
prime[2]=0;

# disregard multiples of primes
for (( i = 3; i < size / 2; i += 2 )); do
    if (( prime[i] )); then
        (( gross += i ));
        for (( j = i * 2; j < size; j += i )); do
            prime[$j]=0;
        done
    fi
done

# continue the sum
for (( ; i < size; i += 2)); do
    (( prime[i] )) && (( gross += i ));
done

# print out
echo $gross;

Anyone have any suggestions? I’m all ears!