So a big part of all this Project Euler nonsense includes prime numbers. Problem 10, begs the ever-so-common question Find the sum of all the primes below one million. Obviously, the first attempt would be to just straight out calculate it using my previous program in Problem 3. Adapting that program to one million integers resulted in about 768 seconds (read: over 10 minutes) of time. Obviously this breaks the 1 minute rule the program needed to be tweaked.

Trying other various methods I still came up short with the result being about 176 seconds at best. To optimize my program I was mainly looking for some information on how prime numbers might be related to bits/bytes to see if I could perhaps try some bitwise operations to speed things up. In doing so, I came across an article suggesting that having an array of bits (essentially a long char) with each char representing a number in an array from 0 to x; x being the limit. Once this array was created, simply just iterate from 0 to the square root of your limit, and mark all multiples of any primes found on your way. Makes sense - and this greatly cuts down on all the harsh prime calculating going on in the background.

As I'm still learning python, I figured I'd try the next best thing and just make an array of boolean variables. This way I can just check to see if they're true/false. After adapting my program to do this -  having a representative array as opposed to an array of actual values, the finished product was able to find the answer in 2 to 3 seconds. Awesome.

Code is posted below. Sooner or later I'm hoping these problems will force me into creating more of an OO type program. But for the time being I'm being pretty lame and writing everything procedurally. As always, comments/criticism is welcome!

Problem 10

Calculate the sum of all the primes below one million.

#!/usr/bin/python#function to find if a number is prime

def is_prime(n):

#check found prime numbers first

  global primes

  for prime in primes:

    if(n%prime == 0):

      return False

  return True

#function to mark prime numbers

def mark_primes(n):

  global numbers

  x = 2

  while(x*n < 1000000):

    if(numbers[x*n]):

      numbers[x*n] = False

    x += 1

#initialize vars

total   = 0

numbers = []

primes  = []

#initially set everything to true

for x in xrange(0, 1000000):

  numbers.append(True)

#we know 0 and 1 are false

numbers[0] = False

numbers[1] = False

#start with multiples of primes from 2 to 1000 (sqrt 1,000,000)

for x in xrange(2, 1000):

#if prime, add to prime pool and mark it and it's multiples

  if(is_prime(x)):

    primes.append(x)

    mark_primes(x)

#calculate the final sum

for x in xrange(0, len(numbers)):

  if(numbers[x]):

    total += x

print "Total: ", total