Sound and Fury

Signifying nothing

Python and primes

leave a comment »

Today I spent a while reaqcuainting myself with Python and IDLE and trying the first few project Euler challenges. I decided it would be worthwhile to have a list of the first few prime numbers, that would make my job easier for several of the problems. (I don’t care if that’s cheating, I still had to make the list of primes…) So I wrote a program to find primes. It’s tremendously inelegant and probably terrible inefficient, but I’m only going for the primes under 10,000 or so. It doesn’t take long to get them. Then I decided to write something that would find the prime factors of an input. The idea is that if the number to factorise is bigger than the biggest prime in the list, it will run the “find primes” program, until it has big enough primes. Anyway, I haven’t got there yet because it’s late and my brain won’t work properly any more. But I do have a number that will give you prime factors, as long as you give it small enough inputs. To try it out, I ask it for the prime factors of the first number to come into my head: 24. [2,3]. Awesome. Now, try it on something bigger. 2400? [2,3,5] hm. Try something else 24001. Too big. 2401 [7] Whaat? What are the odds of my pick 7^4 to test a prime factorisation program. Anyway, eventually I found a number random enough to satisfy me that the thing was working…

The thing is, the whole thing kind of pulls iteslf up by its bootstraps. So if, somehow, a number that isn’t prime crept into the list or a prime was missed out, the whole thing would be invalid. Because it only checks for divisibility of numbers in the list of primes… I should write some sort of consistency check program to make sure all the numbers in the list are not divisible by any of the smaller numbers in the list.


Written by Seamus

August 24, 2008 at 10:06 pm

Posted in maths, python

Tagged with , , ,

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: