Project Euler Problem 3

For project Euler problem 3 we work on a few basic principles that we will use for several upcoming problems (yay reusable code!), factorization and determining whether a number is prime. Here is the problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

One way one could complete this problem would be to find all factors of the given number, and loop through checking if they are prime, returning only the largest one. To start out, let’s find all factors of a number.

import math
def findAllFactors(number):
factors = list()
for i in xrange(1, long(math.sqrt(number))):
if number%i == 0:
factors.append(i)
return factors

Here, we are simply looping through the numbers between 1 and the square root of the number, looking for numbers that divide evenly into our original number. Numbers that divide evenly are factors, so we add them to a list which we return afterward. Alternately, we could create a generator to return all factors:

import math
def findAllFactors(number):
for i in xrange(1, long(math.sqrt(number))):
if number%i == 0:
yield i

Next, we loop through each factor, checking to see if it is prime using the following code:

def isPrime(n):
n = abs(long(n))
if n < 2:
return False
if n == 2:
return True
if not n & 1:
return False
for x in range(3, long(n**0.5)+1, 2):
if n % x == 0:
return False
return True

If we have a prime factor, let’s toss it in a list for now:

if __name__ == "__main__":
factors = findAllFactors(600851475143L)
primeFactors = list()
for f in factors:
if isPrime(f):
primeFactors.append(f)

or if you are using the generator:

if __name__ == "__main__":
primeFactors = list()
for f in findAllFactors(600851475143L):
if isPrime(f):
primeFactors.append(f)

Now we simply grab the largest number in the list by sorting it and grabbbing the last item!

primeFactors.sort()
print "The Correct answer is: %d" % (primeFactors[-1])

Learn to Program with Python pt. 1

Programming can be a fun hobby and a well paying career for those who learn to do it well, as well as a great way to keep stimulating your brain to keep you sharp and alert. Learning to program on your own can be difficult for some people however. Many programming tutorials have one of the following issues:

• Talking above your head: Many programming tutorials assume a great deal of knowledge beforehand, and are therefore not suitable for brand-new programmers
• Being half-heartedly written: Many tutorials start out well, but as the tutorial drags on the author loses interest, and the writing and content suffer dramatically
• Generally sucking: That pretty much sums it up

I have decided to take my own crack at a programming tutorial, and I will attempt to avoid the previously mentioned pitfalls. There are a few details I would like to cover before we get started. The first is my choice of language. I have chosen to use Python for this tutorial for several reasons, the first and foremost being that I really enjoy programming in Python. I also think Python is great about getting out of your way and letting you program without having to micro-manage details such as Data Types (most of the time) and memory allocation (don’t worry if you don’t know what this means). The next detail I would like to cover is the timeline for this tutorial. I plan on writing this tutorial as multiple blog posts over the next several months, with many unrelated posts in between. If it has been a while, feel free to drop me a comment nagging me for the next issue.

Enough introduction, let’s get started with Programming and Python. To get started, we need to make sure we have Python installed on our system. If you are running Linux, chances are Python is pre-installed. For Windows and Mac users, I recommend ActivePython. ActivePython will install Python to your system, as well as a very basic Python editor (although any text editor will do). Open up your editor of choice and type the following:

print "Goodbye Cruel World"

Now save this as emoProgram.py . This is your first program. Kinda lame isn’t it? Don’t worry, you’ll be writing slightly less lame programs in no time. In fact, the only reason I had you do this is so I could teach you to run your program once you have written it. If you are using PythonWin editor (the editor that came with ActivePython) press Ctrl+R and a box will pop up asking you which file you want to run, and it should have emoProgram.py selected. Press OK, and it will run. If you have chosen to use a different editor (or even if you just like the command line), open up a command prompt and navigate to the folder where you saved your script and type:
python emoProgram.py
and you will see “Goodbye Cruel World” print to your terminal.

In an attempt to make each section as short as possible, I will be stopping here for now and picking up again in a few days with variables, operators, and data types.

My first “real” Python Program pt. 2

In the first post about my first real Python program, I talked about how I parsed out stories based upon a tag-based markup system, prompted the user for values for all of the tags, and then returned the story with all user input in place. Today I will be talking about how I created a system to allow users to write their own stories and have them automatically detected and parsed, as well as allowing users to save their created stories.
(more…)

My first “real” Python Program pt. 1

Whenever I start learning a new programming language, I like to start off with a project to get used to the syntax of the language without having to deal with finding holes in my logic. Typically, this program has been a simple “Mad-Libs” style program in which I prompt the user for some words and insert them into a (sometimes) hilarious story. For the most part in the past, these have been statically written stories in which I hard code variable names into a string and write custom prompts for each variable. When starting out in Python, I decided this would not be enough of a challenge. Somewhere between PHP and C# in my language path I hit a point where programming started to make sense on a deeper level. Adding new object types to my repertoire was becoming an everyday occurrence, I began branching out from what I had been taught in programming classes, and creating and dealing with objects dynamically in loops without ever knowing their names became the norm, and no longer blew my mind.
(more…)

Python “yield” and Project Euler problem 2

When working on Project Euler problem 2, I stumbled on a unique feature of Python: the yield keyword. The yield keyword allows for the creation of generators. Generators are defined much like functions, but have the added bonus of being able to return multiple values over the course of their execution. For example, lets say I wanted to make a function that counted from 0 to infinity, and kept it’s state between uses. The following generator would do just that:

def counter():
a = 0
while True:
yield a
a += 1

Simple isn’t it? Iterating through it is simple too. Let’s say we want to get the first 10 numbers, and then the next 20, with a break in between:

if __name__ == "__main__":
x = counter()
for i in x:
if i < 10:
print i
else:
break
print "Broken out of counter"
for i in x:
if i < 30:
print i
else:
break

The output would be:

0
1
2
3
4
5
6
7
8
9
Broken out of counter
11
12
13
.
.
.
23
24
25
26
27
28
29

Now to make this relevant. Project Euler problem 2 is as follows:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

So what we need to do is find a way to take the starting values of 0 and 1, and as each iteration passes, set a to the value of b, and b to the value of a+b, returning a each time. Sounds like a job for generators!

def fibonacci(max):
a, b = 0, 1
while a < max:
yield a
a, b = b, a+b

Next, we loop through each of the returned values, checking if it is even. If so, add it to a running total.

def sumEvenFibonacciNumbers(max):
number = 0
for n in fibonacci(max):
if n%2 == 0:
number += n
return number

if __name__ == "__main__":
print sumEvenFibonacciNumbers(4000000)

There you have it, using generators Project Euler problem 2 was a breeze!

Getting Started with Project Euler

If you haven’t already, go ahead and sign up at Project Euler. Once you have logged in, head on over to the Problems page. I recommend sorting the problems by ascending difficulty, as this will allow you to tackle the problems in a (more or less) gentle slope, at least at first. Let’s take a look at the first problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

So where do we get started? The key to this problem is the modulo operator. For those who are unfamiliar with the modulo operator (notated in many languages as % ), it divides two numbers and returns the remainder. So, if a number divides evenly by 3 or 5, we want to add it to a running total. So, if we were to look at this problem in language-agnostic pseudo-code we would get:

for each number between 0 and 1000
if number/3 evenly, or number/5 evenly
add the number to a running total
print the total to the user

With that, you should be able to complete this problem fairly quickly. If you would like to see this problem implemented in a few programming languages, hit the Read link below:
(more…)

Project Euler and Learning Python

A few months ago I decided it was time to start learning Python. I had heard great things about python,

It's the Python

and I couldn’t in good conscience let an opportunity pass to learn a new language. I grabbed a copy of “Dive Into Python” from the internet (see the link on my sidebar) and got started. I spent a few days writing simple apps going along with the book, but got bored fairly quickly. As someone who has conquered several programming languages at this point, it is difficult to find your mind stimulated by programs designed for new programmers. After a few Google searches, I stumbled upon Project Euler. For those who are not familiar with Project Euler, it is a collection of language-agnostic programming/math problems that are designed to help programmers keep (or develop) their edge. Each problem is designed in such a way that an efficient algorithm should provide the correct answer in 60 seconds or less in any language. I decided to give it a go, and have enjoyed myself greatly in the process. I plan on attempting to complete each challenge in a variety of languages, in an attempt to compare and contrast each language. How many of you have tried Project Euler, and what has your experience been?