CODEWITHSUNDEEP
pythonprimes
supersmarty1234
supersmarty1234

Reputation: 204

Python List (with prime numbers)

I am a beginner at Python, and I need help fixing this piece of code i have created. Bassicaly, I have my code here below. 

import math

def generate_p(p, Count, X, List):
    while Count <= X:
        isprime = True
        for x in range(2, int(math.sqrt(p)) + 1):
            if p % x == 0:
                isprime = False
        if isprime:
            Count += 1
            print p
            P.append(p)
        p += 1

if __name__ == "__main__":
    p = 2
    count = 1
    X = int(raw_input('number: '))
    List = []
    generate_p(p, count, X, List)

Basically, The function does work, however, it does not function how i want it to function. First, i will say how the function's logic work, since the second part of the code is just variables and declaring the function.
while the variable count is less or equal to X, is prime is true, as long as p (the number being tested) can go into every x without a remainder (x is in a range of 2 through the square root of p). If it is prime, add 1 to the count, print the prime, add it too the list, and then and 1 to p, the number being tested. If it is not prime, then just add 1 to p. This keeps going until Count is greater than X, then the code stops.
As you have probably noticed by now, there is a list collecting prime numbers, however, this is mostly being unused. What i want to do, but I don't know how to do, is fix this part of the code, 

for x in range(2, int(math.sqrt(p)) + 1):
    if p % x == 0:
        isprime = False

so that x is in the range of 2 and the square root of p+1, however, i only want x to be numbers in that range that are in the list of P. Can anyone help me do this, and maybe point out any other things in this code?

Upvotes: 0

Views: 1571

Answers (6)

Haukland
Haukland

Reputation: 755

If you want to optimize the function with regards to time complexity when p is large, I would recommend looking into Fermats primality test, or the Soloway strausse test for primality. Additionally a list of common divisors might come in handy!

Upvotes: 0

CromeX
CromeX

Reputation: 445

See if you can wrap your noodle around this generator... The fastest one yet.

def isprime(value):
    stack = [0 for i in xrange(value*2)]
    for jump in xrange(2,value,1):
        for i in xrange(jump,value*2,jump):
            stack[i] += 1
    if stack[value] > 1:
        return False
    else:
        return True

At least my fastest method. Much faster than checking each number

Upvotes: 0

Serge Ballesta
Serge Ballesta

Reputation: 148910

I think that your are looking for the sieve of Eratosthenes algorythm. A python implementation could look like :

 def erato(n):
    "Compute all prime numbers less than or equal to n"
    # utility functions in order to work only with numbers starting at 2
    def prime(i):
        return isprime[i - 2]
    def setprime(i, val):
        isprime[i - 2] = val
    # suppose all numbers may be primes until we find divisors
    isprime = [ True for i in range(2, n+1) ]
    for i in range(2, int(math.sqrt(n)) + 1):
        # do not process non prime numbers
        if prime(i):
            # if i is prime, all its multiples are not
            j = 2 * i
            while j <= n :
                setprime(j, False)
                j += i
    # return the list of prime numbers
    return [ i for i in range(2, n + 1) if prime(i) ]

Upvotes: 0

zehnpaard
zehnpaard

Reputation: 6223

While the other answers are correct in terms of logic, they will evaluate every item in P for its size. If P is sorted in ascending order of size, and P is sufficiently large, then it might be more efficient to just loop through P and include a break clause at the top of the loop.

Edit Actually to do this, you would need to split this section off into its own function so that you don't terminate the top-level while loop. Then you just return True/False at each point

def is_prime(x, P):
    sqrt_p = int(math.sqrt(p)) + 1
    for x in P:
        if x > sqrt_p:
            return True
        if p % x == 0:
            return False
    return True

In terms of other observations:

  1. Try using better names. X, List, P, p etc make for difficult code to debug and modify. In fact, you're sending List into the function but don't do anything with it - I guess P and List are supposed to be the same thing. Variable confusion can be mitigated/spotted more easily with names like upper_bound, prime_list, prime. Also check PEP8 for general naming conventions in Python that will make your code more readable and consistent for other Python programmers.
  2. Instead of creating an empty list outside the function and then sending it in as an argument, it might be better to create the list within the function, append all the primes found, and have the function return the list - it tends to improve readability and reduce the scope for bugs.

Upvotes: 0

Barry
Barry

Reputation: 303087

If you want to just iterate over the numbers in P that are less than or equal to the square root of p:

for x in (i for i in P if i <= math.sqrt(p)):
    if p % x == 0:
        isprime = False
        break # can stop here

Note that having p and P as variables is very confusing.

Upvotes: 2

zmbq
zmbq

Reputation: 39013

You can use List Comprehension, like so:

for x in [prime in P if prime<=math.sqrt(p)]:
    ...

Upvotes: 2

Related Questions