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

Join Date
Apr 2013
Posts
2
Rep Power
0

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. 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!!
3. 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
4. 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 04:53 PM.
5. 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 10:19 PM.