You should reset c
to zero before the beginning of each inner loop:
nums = []
for a in range(1,11):
c = 0
for b in range(1,11):
if a%b==0:
c = c+1
if c==2:
nums.append(a)
for d in nums:
print d
Additionally, you should use print d
, since the for
-loop already gives every element in nums
.
Using a list comprehension is generally faster and considered more pythonic than using a for
-loop.
There are many different ways of calculating prime numbers. Here are some of them.
Here is your original algorithm, with some improvements;
def prime_list(num):
"""Returns a list of all prime numbers up to and including num.
:num: highest number to test
:returns: a list of primes up to num
"""
if num < 3:
raise ValueError('this function only accepts arguments > 2')
candidates = range(3, num+1, 2)
L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))]
return [2] + L
- For primes >2, they must be odd numbers. So
candidates
should contain only odd numbers. - For an odd number
c
to be prime, one must ensure thatc
modulo all previous odd numbers (p
) must be non-zero. - Lastly, 2 is also prime.
A further improvement is to restrict p
up to sqrt(c)
:
import math
def prime_list2(num):
if num < 3:
raise ValueError('this function only accepts arguments > 2')
candidates = range(3, num+1, 2)
L = [c for c in candidates if all(c % p != 0 for p in
range(3, int(math.sqrt(c))+1, 2))]
return [2] + L
Another implementation:
def prime_list3(num):
num += 1
candidates = range(3, num, 2)
results = [2]
while len(candidates):
t = candidates[0]
results.append(t)
candidates = [i for i in candidates if not i in range(t, num, t)]
return results
This starts off with a list of candidates that contains all odd numbers. Then is calculates a new list of candidates by removing the first number of the previous list and all all multiples of it.
Let's look at the speed of the algorithms.
For small numbers, the original prime_list
is the fastest;
In [8]: %timeit prime_list(10)
100000 loops, best of 3: 8.68 µs per loop
In [9]: %timeit prime_list2(10)
100000 loops, best of 3: 10.9 µs per loop
In [10]: %timeit prime_list3(10)
100000 loops, best of 3: 8.96 µs per loop
For larger numbers, prime_list2
comes out the winner:
In [5]: %timeit prime_list(1000)
100 loops, best of 3: 8.28 ms per loop
In [6]: %timeit prime_list2(1000)
100 loops, best of 3: 2.46 ms per loop
In [7]: %timeit prime_list3(1000)
10 loops, best of 3: 23.5 ms per loop
In [11]: %timeit prime_list(10000)
1 loops, best of 3: 646 ms per loop
In [12]: %timeit prime_list2(10000)
10 loops, best of 3: 25.4 ms per loop
In [13]: %timeit prime_list3(10000)
1 loops, best of 3: 2.13 s per loop