Python Prime finder on the Raspberry Pi

[Tryzan50]

Hi all,
I've been looking for primes on my pi (model b) using python. Here is my current program:

f = open("primesList", "w") #Opens a new blank file to write primes to
f.write("2 \n")

def primeCheck(number, primeList):
->prime = True
->for num in primeList:
->->if number % num == 0:
->->->prime = False
->->->break #Exits the for loop if it is not prime
->->if prime == True:
->->->primeList.append(number)
->->->f.write("%s \n" % str(number)) #Writes to the primeList file

primeList = [2]
number = 1 #Starts at one and then adds 2 to avoid all evens

while len(primeList) < 1000: #Will find the first 1000 primes (can be changed)
->number += 2
->primeCheck(number, primeList)

f.close()


I would like to find the first million primes as a project but, as I am using the pi, it is rather slow. How can I make it faster?

Many thanks

 

[Tryzan50]

Thank you for the very detailed reply

You're initialising the array with a single value and keep on appending to it.

Could I fix this by filling the array with values 2 - 15,485,863 (the millionth prime) at the start of the program using this code:

for x in range(2, 15485863):
->numbersList.append(x)

Then go through the list with the sieve and delete any numbers that are found to be not prime so the list would become shorter with each pass of the sieve - on the first pass the list would start at 15,485,863 values long and end at around 7.5million long and so on?

I will have a go at the Sieve of Eratosthenes in python and post results here.

Thanks again

 

[Tryzan50]

Thanks for the advice peterwalkley I have now changed my program accordingly. I will have a look at those courses.

Program nearly ready

 

[Tryzan50]

Here it is! It is extremely fast, for an input of 100,000 my old program takes around 1min10sec and the new one takes 1.5 seconds!

def eratosthenes(limit):
->valuesList = [False] * 2 + [True] * (limit-1)
->for x in xrange(int(limit**0.5 + 1)):
->->if valuesList[x] == True:
->->->for x in range(x**2, limit + 1, x):
->->->->valuesList[y] = False
->for z in xrange(limit + 1): #Writes to the file at end of program
->->if valuesList[z] == True:
->->->primesFile.write("%s \n" % str(z))

primesFile = open("MorePrimes", "w")
eratosthenes(1000000)

Thanks for all the help guys, any other suggestions for speed?

 

[Tryzan50]

Next, change languages python is terrible for this kind of thing and is best left for scripting and prototyping. A good c implementation is likely 10-20 times faster.

Python is the only language I know, apart from HTML and CSS, and I don't have the time right now to learn a new language

I would concentrate on better coding practices, e.g, there are better ways of doing file IO in python (with open)

Do you know of somewhere where the best coding practices are laid out?

Tryzan, when posting code please use [CODE] tags.

Thank you, I was unaware that this was available

 

[Tryzan50]

I agree, python I used mainly by beginners who do not need speed for their simple programs and therefore don't worry about it. I will try x*x instead of x**2 and edit this post with results.
EDIT:
Using x**2 for an input of 1000000 took an average of 11.957s
Using x*x for an input of 1000000 took an average of 10.385s

I will look at the help pages, thanks for putting me in the right direction.