# Portfolio: Sieve of Eratosthenes

View raw: eratosthenes.py

#!/usr/bin/env python2 # -*- coding: utf-8 -*- # # Copyright by Scott Severance # # Permission is hereby granted, free of charge, to any person obtaining a copy # of this software and associated documentation files (the "Software"), to deal # in the Software without restriction, including without limitation the rights # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be included in # all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN # THE SOFTWARE. # This is a library to implement the Sieve of Eratosthenes # <https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>. # # This module has only been tested in Python 2. No attempt has been made to make # it compatible with Python 3. ''' This module contains functions for handling prime numbers. All prime number operations are done by means of the Sieve of Eratosthenes. Functions: list_primes(upper_limit) Lists all primes up to a given limit is_prime(num) Tests whether a given integer is prime prime_factors(num) Returns a list of num's prime factors ''' import math def list_primes(upper_limit): ''' This function implements the Sieve of Eratosthenes to find all prime numbers up to a given integer. Parameter: upper_limit: the highest integer to search. (raises ValueError if upper_limit < 2 or isn't an integer.) Returns: a list of prime numbers ''' if upper_limit != int(upper_limit): raise ValueError, "%d isn't an integer!" % upper_limit if upper_limit < 2: raise ValueError, "%d doesn't make sense as an upper limit!" % upper_limit loop_limit = math.sqrt(upper_limit) ints = range(2, upper_limit + 1) primes = [] while True: i = ints[0] primes.append(i) del ints[0] if i <= loop_limit: ints = [x for x in ints if x % i != 0] else: return primes + ints # All remaining ints are prime def is_prime(num): 'Tests whether num is prime. Returns bool.' return num in list_primes(num) def prime_factors(num): "Returns a list of num's prime factors." if num != int(num): raise ValueError, "Can't find the prime factors of a non-integer." num = abs(num) try: primes = list_primes(int(math.sqrt(num))) except ValueError: # num is either small or invalid if num == 1: return [num] primes = list_primes(num) factors = [] for i in primes: # I use a while loop instead of an if statement because some # factors might occur more than once. while num % i == 0: factors.append(i) num /= i if num == 1: return factors elif num in primes: break factors.append(num) return factors # For testing purposes, this module can be called directly from the command line # with an integer specified on the command line. Each function in this module # will be called with that integer. Don't try this with too large an integer # unless you have a lot of time to spare. Better to import the module and call # just the functions you need. # # The code below only executes if this module is run directly as opposed to # being imported. if __name__ == '__main__': from sys import argv, stderr, exit if len(argv) != 2: stderr.write('ERROR: You must pass exactly one argument, an integer.\n') exit(1) try: number = int(argv[1]) except ValueError: stderr.write('ERROR: You must pass an integer.\n') exit(1) primes = list_primes(number) print 'Primes up to %d:' % number, primes print '%d is prime:' % number, number in primes print 'The prime factors of %d are:' % number, prime_factors(number)