Thread: Grade Me

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    2
    Rep Power
    0

    Grade Me


    I'm working on learning Python, but I'm not in school or classes. I was just wondering how well I was doing and if this is good or not. I looked up typical assignments students would be given and I started with the list Prime numbers.
    Code:
    from math import sqrt
    
    def Prime_upto(x):
        Primes = [2]
        if x < 2:
            Primes = []
            return Primes
        if x == 2:
            return Primes
        if x > 2:
            for i in range(3, x+1,2):
                if isPrime(i):
                    Primes.append(i)
        return Primes
    
    def isPrime(x):
        if x < 2:
            return False
        if x == 2:
            return True
        for i in range(3,int(sqrt(x))+1,2):
            if x % i == 0:
                return False
        return True
        
    check = int(input("Primes up to: "))
    print (Prime_upto(check))
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,904
    Rep Power
    481
    Your code is good. The answers are correct through 10,000. (compared with primes in j,
    p:i.1229
    www.jsoftware.com
    )

    Sieve is faster:
    Code:
    import array
    sieve = array.array('b',(0 for i in range(1000000)))
    for i in range(2,len(sieve)):
        if not sieve[i]:
            for j in range(i*i,len(sieve),i):
                sieve[j] = 1
    
    sieve[:2] = 1
    
    print([i for (i,p,) in enumerate(sieve) if not p])
    (ha ha I checked my code through 20 "by eye") gotta run!!
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    2
    Rep Power
    0
    Thanks for the feedback! Off to research sieve
  6. #4
  7. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Feb 2005
    Posts
    611
    Rep Power
    65
    Just a housekeeping thing, names starting with a capital letter are generally used for class names.

    Avoid calling functions within a loop, it has a lot of overhead and is slow. Try to role your isPrime() function into the for loop in function Prime_upto().

    If you don't like a sieve approach, you can do something like this ...
    Code:
    def primelist_nosieve(r=10):
        """
        improved version, loop only over odd numbers starting with 3
        and limit divisor range further with **0.5 (square root)
        """
        primes = [2]
        # now ranges return odd numbers only ...
        for i in range(3, r+1, 2):
            prime = 1
            for divisor in range(3, int(i ** 0.5)+1, 2):
                if i % divisor == 0:
                    prime = 0
                    break
            if prime:
                primes.append(i)
        return primes
    This is the fastest straight Python primelist function I know ...
    Code:
    def primelist_sieve__ds(n):
        """
        returns  a list of primes 2 to < n
        """
        sieve = [True] * (n>>1)
        for x in range(3, int(n**0.5)+1, 2):
            if sieve[x>>1]:
                sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
        return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]
    Last edited by Dietrich; April 7th, 2013 at 03:53 PM.
    Real Programmers always confuse Christmas and Halloween because Oct31 == Dec25
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,904
    Rep Power
    481
    Less interpreting makes quicker execution.
    Code:
    import array
    
    def primes_upto(n):
        zeros = array.array('b',(0,))*(n+1)  ## at the expense of more memory
        sieve = array.array('b',(1,))*(n+1)
        for i in range(2,len(sieve)):
            if sieve[i]:
                sieve[i*i::i] = zeros[i*i::i] ##### this was an explicit loop
        return [i+2 for (i,p,) in enumerate(sieve[2:]) if p]
    
    print(primes_upto(int(input('upto...'))))
    Last edited by b49P23TIvg; April 6th, 2013 at 09:19 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo