# Duncan's blog

## October 25, 2008

### Project Euler: problem 7

Problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Prime numbers again, good job I spent so long trying various things out on problem 3. I just copied the IsPrime function I did then (except removed the custom Mod function and just used CF’s MOD, as we’re dealing with smaller numbers here).

I’m using a brute force method of continually looping, building up an array of primes, until we get to the 10001st one. This time, as we know primes start at 2, but are odd after that, I decided to pre-populate my array with 2, and then loop in steps of 2 from 3 upwards.

```<cfset primes = ArrayNew(1)>
<cfset limit = 10001>
<cfset done = 0>
<cfset i = 1>
<cfset ArrayAppend(primes, 2)>

<cfscript>
function isPrime(x)
{
var isPrime = true;
var i = 0;

if (x LT 2)
{
return false;
}

if ((NOT x MOD 2) AND (x GT 2))
{	// a multiple of 2, but not 2 itself
return false;
}

for (i = 3; i LTE SQR(x); i = i + 2)
{
if (NOT x MOD i)
{	// found a factor of x
return false;
}
}

return isPrime;
}
</cfscript>

<cfloop condition="NOT done">
<cfset i = i + 2>

<cfif IsPrime(i)>
<cfset ArrayAppend(primes, i)>

<cfif ArrayLen(primes) EQ limit>
<cfset done = 1>
</cfif>
</cfif>
</cfloop>

<cfoutput>
#primes[limit]#
</cfoutput>
```
Advertisements

## 1 Comment »

1. […] previously blogged about this Project Euler puzzle 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

Pingback by Project Euler: problem 7 (PHP) | Duncan's blog — September 25, 2014 @ 8:04 am

Create a free website or blog at WordPress.com.