Python Programming/Loops/Solutions
From Wikibooks, the open-content textbooks collection
1. Create a program to count by prime numbers. Ask the user to input a number, then print each prime number up to that number.
For this program we will make a list of possibilities up to the user's input, then test each one using Fermat's little theorem, adding the primes to a list of primes. Finally we print the list of primes.
Comment: This program is not correct, while all primes fulfil Fermat theorem, but also some "pseudoprimes" which are not primes (e.g. 341=11*31) do it also: (((2**341)-2)%341 == 0) see more: http://primes.utm.edu/prove/prove2_2.html
See the comments for more information.
primes = [] # Creates a list that we will throw our prime numbers into. user = 1 + int(raw_input("What number would you like to count primes up to? ")) # 1 is added on to the user's number so that their number # is counted. list = range(2,user) # 0 and 1 are not prime, but our algorithm registers them # as prime, so we start with two for possibility in list: if ((2**possibility)-2)%possibility == 0: # Our algorithm (Fermat's little theorem) states # that if "i" is an integer and i^p-i divides evenly # into p, p is prime. We are using 2 in place of i. # See Python Programming/Basic Math for more info. primes.append(possibility) # We add each prime to the primes list. print ("The prime numbers from 0 to", user-1, "are: ") for possibility in primes: print possibility # Print out all the primes!
