HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Generating a list of primes of a given length

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
primeslengthgeneratinglistgiven

Problem

After considerable effort, I've come up with the following code to generate a list of primes of a given length.

I would be very interested to see how an experienced coder would modify my code to make it more readable, more concise, or somehow better. I won't be able to follow fancy-pants coding that doesn't involve basic iterations of the type I have used, so please keep it simple for me. I've been learning the language only a few months.

Function returns number of primes indicated in call.

Algorithm: Add two to last candidate in list (starting with [2, 3, 5]) and check whether other members divide the new candidate, iterating only up to the square root of the candidate.

import math
def primeList(listLength):
    plist = [2, 3]
    j = 3
    while listLength > len(plist):
        prime = 'true'
        i = 0
        j +=2
        plist.append(j)
        while plist[i] <= math.sqrt(j) and prime == 'true':
            if j%plist[i] == 0:
                prime = 'false'
            i +=1
        if prime == 'false':
            plist.pop(-1)         
    return plist

Solution

Don't be afraid of typing. Longer names are more readable and should be used except for simple counters. Split out complicated sub-parts where they are separate concepts.

Here is how I would improve it:

import math

def isPrime (primeList, candidate):
    upperLimit = math.sqrt(candidate)
    for p in primeList:
        if candidate % p == 0:
            return False
        if p >= upperLimit:
            break

    return True

def primeList(listLength):
    if listLength  len(primes):
        if isPrime(primes, candidate):
            primes.append(candidate)
        candidate +=2

    return primes


To make a faster simple prime algorithm, consider the other naive algorithm in the primality test wikipedia article where all primes are of the form 6k +- 1.

Code Snippets

import math

def isPrime (primeList, candidate):
    upperLimit = math.sqrt(candidate)
    for p in primeList:
        if candidate % p == 0:
            return False
        if p >= upperLimit:
            break

    return True

def primeList(listLength):
    if listLength < 1 :
        return []
    primes = [2]

    candidate = 3
    while listLength > len(primes):
        if isPrime(primes, candidate):
            primes.append(candidate)
        candidate +=2

    return primes

Context

StackExchange Code Review Q#28537, answer score: 5

Revisions (0)

No revisions yet.