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>

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 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: