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

Hello all,

First post on the forum! Nice to meet you

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!

1 Like