First let's take a second to think about your current approach.

• For each time the outermost loop iterates you loop n-2 times over the inner loop.
• For each time the inner loop iterates you loop over each item in results. (include? is most likely doing at least some kind of looping under the hood. How efficient the algorithm is I don't know.)

So, the first obvious optimization to make is to special case the number 2 as it's the only even prime number. Add it directly to your final list_of_primes from the get go. Then you only have to check every other number in your inner loop. In other words, increment by two instead of one.

(3..(i - 1)).step(2) do |j| 

The second thing to do is to get rid of the intermediate results (and thus another, albeit implicit loop). You can do this by checking each i To see if it's prime. A naive approach is to check its modulus against each number less than j and break from the inner loop if it's equal to zero.

 if (i % j == 0) then isPrime = false break end end list_of_primes >> i if isPrime 

Now, I say this is naive only because we don't have to check each number up to j. We only need to loop up to the square root of j. If j isn't divisible by a number less than or equal to its square root. It's prime. Go ahead. Go check. I'll wait.

...

Pretty cool, eh?

Anyway, there are other completely different algorithms for this. Typically, when searching for all the prime numbers up to n, we'd use the Sieve of Eratosthenes.

Lastly, I apologize if my syntax is wrong or the code isn't very idiomatic. It's been a long time since I wrote any Ruby and I never was very good at it. Hopefully this still helps.

First let's take a second to think about your current approach.

• For each time the outermost loop iterates you loop n-2 times over the inner loop.
• For each time the inner loop iterates you loop over each item in results. (include? is most likely doing at least some kind of looping under the hood. How efficient the algorithm is I don't know.)

So, the first obvious optimization to make is to special case the number 2 as it's the only even prime number. Add it directly to your final list_of_primes from the get go. Then you only have to check every other number in your inner loop. In other words, increment by two instead of one.

(3..(i - 1)).step(2) do |j| 

The second thing to do is to get rid of the intermediate results (and thus another, albeit implicit loop). You can do this by checking each i To see if it's prime. A naive approach is to check its modulus against each number less than j and break from the inner loop if it's equal to zero.

 if (i % j == 0) then isPrime = false break end end list_of_primes >> i if isPrime 

Now, I say this is naive only because we don't have to check each number up to j. We only need to loop up to the square root of j. If j isn't divisible by a number less than or equal to its square root. It's prime. Go ahead. Go check. I'll wait.

...

Pretty cool, eh? So, your inner loop would end up looking something like this.

 (3..(Math.sqrt(i))).step(2) do |j| 

Anyway, there are other completely different algorithms for this. Typically, when searching for all the prime numbers up to n, we'd use the Sieve of Eratosthenes.

Lastly, I apologize if my syntax is wrong or the code isn't very idiomatic. It's been a long time since I wrote any Ruby and I never was very good at it. Hopefully this still helps.