Project Euler: problem 10

This one had me stumped for a while. The code isn’t that difficult, but making something that can run efficiently on my old CF 5 server seemed a bit trickier. In the end I used something that took ages to run, and decided to refactor my code once I’d read some of the discussions you get access to after completing these problems.

Problem 10:

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

Find the sum of all the primes below two million.

The brute force way to do this would be to loop from 1-2000000, checking if each number is prime before adding it to your total. A slightly less brute method would be to do it in steps of 2, avoiding the even numbers (except 2). I tried to avoid doing that, using various methods I’d already been using in earlier ones, trying to apply the Sieve of Eratosthenes, stepping in sixes, etc but with no luck. So I went back to the brute force, which took many minutes. Then rewrote my code.

I initially hadn’t been too far away from getting the solution, just needed a bit of tidying up. Here’s the revised code:

<cfset limit = 2000000>
<cfset numbers = ArrayNew(1)>

<!--- initialise our array --->
<cfset ArraySet(numbers, 2, limit, 1)>

<!--- switch off all the even numbers except 2 --->
<cfloop index="i" from="4" to="#ArrayLen(numbers)#" step="2">
	<cfset numbers[i] = 0>
</cfloop>

<!--- we only need to loop up to the root of our limit --->
<cfloop index="i" from="3" to="#SQR(limit)#" step="2">
	<cfif numbers[i]>
		<cfloop index="j" from="#(i * i)#" to="#limit#" step="#(2 * i)#">
			<cfset numbers[j] = 0>
		</cfloop>
	</cfif>
</cfloop>

<cfset sum = 0>

<cfloop index="i" from="2" to="#limit#">
	<cfif numbers[i]>
		<cfset sum = sum + i>
	</cfif>
</cfloop>

<cfoutput>#sum#</cfoutput> 

I’m still lacking a true understanding of how to generate prime numbers efficiently. The things that I didn’t get right in my first go round:

• only looping to the square root of our limit
• not needing to actually check if a number is prime
• the values for the from and step attributes in this line:
  <cfloop index=”j” from=”#(i * i)#” to=”#limit#” step=”#(2 * i)#”>
  I had them as from=”#(i * 2)#” and step=”#i#”

Interestingly, at one point I rewrote my code from normal CFML syntax to all be in CFScript, thinking that perhaps multiple <cfset> statements would run faster like this. That used to be the conventional wisdom in CF 5; multiple cfsets should be moved to a cfscript block; but no longer applies in CFMX. However I found it took almost twice as long to run.