4
\$\begingroup\$

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

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()
\$\endgroup\$
1

2 Answers 2

7
\$\begingroup\$

Welcome to programming and code review!

Your code is pretty good especially for a beginner, but I'm going to be picky:

from time import time

I recommend putting at least one blank line between the imports and the code proper

odd = 1

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.

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 primes

global 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.

\$\endgroup\$
0
\$\begingroup\$

To format your code in python is to write it so you have your title/author comments on top, imports below, classes, functions and then your main.

Generally is is considered poor coding prose in python mainly because it attracts unnecessary bugs. is compares two objects in memory, == compares their values, with the latter as what coder usually means.

A global variable here is completely unnecessary, there are few cases when it is useful and this is definitely not one of them. Just send it as an argument.

i*i can be rewritten as i**2

Other than that and what Winston mentioned, very impressive for a beginner. Keep going!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.