My backwards logic

Paul Rubin no.email at nospam.invalid
Fri Sep 5 22:07:41 CEST 2014


Juan Christian <juan0christian at gmail.com> writes:
>  I made this code just for fun and learning, it's working, but would
>  this be a good approach? Thanks. ...
>  ** ** for number in range(start, stop + 1):
>  ** ** ** ** divisors = [(number % x) for x in range(1, number + 1)]
>  ** ** ** ** ** ** print("{n} prime? {r}".format(n = number, r =
>  (divisors.count(0) == 2)))

1. Mathematically it's better to stop checking once you've gone past
the square root of the number, since if n = p*q and is composite,
then at least one of p,q will be <= sqrt(n).

2. As a program design matter, it's generally preferable for functions
like this to not print the answer.  They should just return a value, in
this case a bool indicating whether the number is prime.  That makes it
easier to re-use the function, to wrap it in a unit test framework, etc.
If you want to print the result, then call the function and have the
caller print the returned value.

3. As a simple optimization, once you have checked that the number is
not divisible by 2, you don't have to check for other even divisors.
So just check for 2, then the odd numbers 3,5,7...

This is a little bit fancy but I like to use itertools for these
sorts of problems:

  from itertools import chain, takewhile, count

  def is_prime(n):
      if n < 2: return False
      candidates = chain([2], count(3,2))
      return all(n%d!=0 for d in takewhile(lambda d: d*d<=n, candidates))

If you're not familiar with those functions, "chain" concatenates
two sequences, and "count(n,i)" gives an increasing sequence starting
with n and incrementing by i.  So chain([2], count(3,2)) gives
the unending sequence [2, 3, 5, 7, 9, ...] which is the numbers
you want to check against.  Then the takewhile expression chops
that sequence once it gets past sqrt(n), and "all" returns true iff
all of the candidate divisors fail to divide the number.



More information about the Python-list mailing list