patternpythonMinor
Optimizing this 'print up to the nth prime number' script
Viewed 0 times
thisnthscriptthenumberprintoptimizingprime
Problem
I've been seeking to optimize this algorithm, perhaps by eliminating one of the loops, or with a better test to check for prime numbers.
I'm trying to calculate and display 100000 prime numbers has the script pausing for about 6 seconds as it populates the list with primes before the primes list is returned to the console as output.
I've been experimenting with using
to simply print every found prime number, which is faster for smaller inputs like n = 1000, but for n = 1000000 the list itself prints much faster (both in the Python shell and in the console).
Perhaps the entire code/algorithm should be revamped, but the script should remain essentially the same: The user types in the number of prime numbers to be printed (n) and the script returns all prime numbers up to the nth prime number.
I'm trying to calculate and display 100000 prime numbers has the script pausing for about 6 seconds as it populates the list with primes before the primes list is returned to the console as output.
I've been experimenting with using
print odd,to simply print every found prime number, which is faster for smaller inputs like n = 1000, but for n = 1000000 the list itself prints much faster (both in the Python shell and in the console).
Perhaps the entire code/algorithm should be revamped, but the script should remain essentially the same: The user types in the number of prime numbers to be printed (n) and the script returns all prime numbers up to the nth prime number.
from time import time
odd = 1
primes = [2]
n = input("Number of prime numbers to print: ")
clock = time()
def isPrime(number):
global primes
for i in primes:
if i*i > number:
return True
if number%i is 0:
return False
while len(primes) < n:
odd += 2
if isPrime(odd):
primes += [odd]
print primes
clock -= time()
print "\n", -clock
raw_input()Solution
Welcome to programming and code review!
Your code is pretty good especially for a beginner, but I'm going to be picky:
I recommend putting at least one blank line between the imports and the code proper
You don't use this until much later. Don't declare variables until you actually need them. It will make the code easier to read.
Rather than using input, I recommend using int(raw_input(. Input actually interprets the text entered as a python expression which means it can do anything. If you really just wanted a number, using int(raw_input is better. Also, input has been modified in python 3 to be like raw_input.
Typically functions are defined before the actual code not in the middle of it.
global is only necessary if you want to modify the primes. Since you don't modify it, you don't need it.
It's not immediately obvious why you can stop here. A comment would be helpful.
Put spaces around your operators: %
When adding a single element to a list use primes.append(odd)
That's kinda confusing. I'd suggest doing start_time = .., end_time = ..., time_spent = end_time - start_time. That ways it clear what you are doing, whereas what you've done with the clock is unusual and not immeadiately obvious.
Also, don't put logic in the top level scope of your program. Put all logic especially loops inside a function. It'll run faster in the function, and will keep the program neater.
Your code is pretty good especially for a beginner, but I'm going to be picky:
from time import timeI recommend putting at least one blank line between the imports and the code proper
odd = 1You don't use this until much later. Don't declare variables until you actually need them. It will make the code easier to read.
primes = [2]
n = input("Number of prime numbers to print: ")Rather than using input, I recommend using int(raw_input(. Input actually interprets the text entered as a python expression which means it can do anything. If you really just wanted a number, using int(raw_input is better. Also, input has been modified in python 3 to be like raw_input.
clock = time()
def isPrime(number):Typically functions are defined before the actual code not in the middle of it.
global primesglobal is only necessary if you want to modify the primes. Since you don't modify it, you don't need it.
for i in primes:
if i*i > number:It's not immediately obvious why you can stop here. A comment would be helpful.
return True
if number%i is 0:Put spaces around your operators: %
return False
while len(primes) < n:
odd += 2
if isPrime(odd):
primes += [odd]When adding a single element to a list use primes.append(odd)
print primes
clock -= time()That's kinda confusing. I'd suggest doing start_time = .., end_time = ..., time_spent = end_time - start_time. That ways it clear what you are doing, whereas what you've done with the clock is unusual and not immeadiately obvious.
print "\n", -clock
raw_input()Also, don't put logic in the top level scope of your program. Put all logic especially loops inside a function. It'll run faster in the function, and will keep the program neater.
Code Snippets
from time import timeprimes = [2]
n = input("Number of prime numbers to print: ")clock = time()
def isPrime(number):global primesfor i in primes:
if i*i > number:Context
StackExchange Code Review Q#3833, answer score: 7
Revisions (0)
No revisions yet.