A prime number is a positive integer that has no positive integer divisors except for itself and 1. For example, 5 is a prime number because (a) it’s a positive integer, and (b) its only positive integer divisors are itself and 1. On other hand, 12 is not a prime number because it has positive integer divisors 1, 2, 3, 4, 6, and 12. Positive integers that are not prime are called composite.
The smallest prime number is 2. The integer 1 is neither prime nor composite—it’s placed in a category by itself. After 2, all prime numbers are necessarily odd, since all even integers have 2 as a divisor.
The fundamental theorem of algebra states that any positive integer can be written in exactly one way as a product of prime numbers. For example, 1,092 can be written:
1,092 =2 x 2 x 3 x7 x 13
There is no simple method of generating the prime factors of a given integer, a fact which forms the basis of RSA encryption. (Well, there is known method.) There are, however, simple methods for generating a list of prime numbers starting with 2 and ending with some upper limit. To my knowledge, such algorithms have almost no practical value. Nevertheless, I offer a super-simple, somewhat slow algorithm here.
Why do I do this? Two reasons. First, I’m bored and I need something to do. Second, programming is one of the few components of my professional work that crosses over into my “hobby zone.” So I want to start sharing some of my simpler codes on my blog.
The code is written in Python, although virtually any language can handle this algorithm. But Python is free and very easy to learn if you’re interested in writing your own programs. I recommend the VPython distribution, which includes libraries that allow you to create simple but powerful 3-D animations. In future posts, I’ll show you how to do this. For now, the Python code for finding prime numbers follows. To run this code, open the IDLE shortcut on your desktop (after installing the files from Vpython.org), cope and paste the code into the window, and save the file. Then hit the F5 key and follow the prompt in the shell window.
"""
find_primes.py
Finds all prime numbers between 2 and a user-supplied
upper limit. Works by brute force.
Rodney Dunning
Assistant Professor of Physics
Longwood University
"""
#-----------------
#
# print_intro
#
#-----------------
def print_intro():
print "This program finds all the prime numbers"
print "between 2 and an upper limit that you provide."
print "It works by brute force, so it's not very fast."
print "" # spacer
#-----------------
#
# get_upper_limit
#
#-----------------
def get_upper_limit():
upper_limit = input("Enter the upper limit: ")
print "" # spacer
print "Your upper limit is ",upper_limit
print "" # spacer
return upper_limit
#-------------------
#
# print_prime(x)
#
#-------------------
def print_prime(x):
print " Found a prime: %12i " %x
#-------------------
#
# find_primes
#
#-------------------
def find_primes(upper_limit):
candidate = 3
while(candidate <= upper_limit):
trial_divisor = 2
prime = 1 # assume it's prime
while(trial_divisor**2 <= candidate and prime):
if(candidate%trial_divisor == 0):
prime = 0 # it isn't prime
trial_divisor+=1
if(prime):
print_prime(candidate)
candidate += 2
#-------------------
#
# main (program)
#
#--------------------
def main():
print_intro()
upper_limit=get_upper_limit()
print_prime(2) # 2 is prime!!
find_primes(upper_limit)
main()
ur website has helped a lot! but im trying to write a python program that inputs a starting number (non-2 number) and an ending number. Then do exactly what this program did to output each prime number withing the starting and stopping close interval. and lastly ask the user if it desires to do another run. I know this is probably something really simple but i dont know python language! and its so confusing! help!!!
Brenda,
I have a feeling you’re asking for help with a homework problem. That’s okay, but you should let your professor know that you’re getting outside help.
To make the changes you need, you can do the following:
(1) Create a new function to ask for the starting value. It will be essentially identical to get_upper_limit, except for the screen prompt. You will also want to include some kind of error check to make sure the user enters an odd number.
(2) Pass two arguments to find_primes, the starting value and the upper limit. In find_primes, instead of initializing candidate to be equal to 3, set it equal to the starting number.
(3) Asking the user if she wants to continue might be a bit tricky. There are several ways to do this, and I will try to post a new article showing an example in a couple of days.
Pingback: Asking the User for Input in Python « Very Important Stuff
“”"
Modified version to find a set number of primes.
#----------------- # # get_limit # #----------------- def get_limit(): limit = input("How many primes do you need?: ") print "" # spacer print limit, "primes coming up" print "" # spacer return limit #----------------- # # print_intro # #----------------- def print_intro(): print "This program finds as many prime numbers" print "as you like." print "It works by brute force, so it's not very fast." print "" # spacer #------------------- # # print_prime(x) # #------------------- def print_prime(x): print " Found a prime: %12i " %x #------------------- # # find_primes # #------------------- def find_primes(limit): counter = 2 candidate = 3 while(counter <= limit): trial_divisor = 2 prime = 1 # assume it's prime while(trial_divisor**2 <= candidate and prime): if(candidate%trial_divisor == 0): prime = 0 # it isn't prime trial_divisor += 1 if(prime): print_prime(candidate) counter += 1 candidate += 2 #------------------- # # main (program) # #-------------------- def main(): print_intro() limit = get_limit() print_prime(2) find_primes(limit) main()Rodney,
Been writing a Python scrip to figure out Fibonacci Prime numbers, however the Fibonacci works and the scrip for prime numbers works, just cannot get them to execute together. Could you take a look. I’ve re-arranged and altered many times here is one of the scripts that has promise yet not the specific needs.
# Defining Functions
def fib(n): # write Fibonacci series up to n
“”"Print a Fibonacci series up to n.”"”
a, b = 0, 1
while b < n:
print b,
a, b = b, a+b
# Now call the function we just defined:
fib(2000)
#! python
# break operator
# prime numbers
for n in range(2, 1000):
for x in range(2, n):
if n % x == 0:
print n, 'equals', x, '*', n/x
break
else:
# loop fell through without finding a factor
print n, 'is a prime number'
Both parts of the code are working, but the prime number part will identify some numbers as prime before it eliminates them. For example, it identifies 15 as prime (temporarily) since it passes the x=2 test in the inner loop. On the next pass, when x=3, it scrubs 15 as a prime number and falls through. So you wound up with a print statement you didn’t need. That’s a minor fix.
It seems what you want to do is create a function that tests only one number to see if it’s prime, instead of sequentially testing all the numbers between 2 and some upper limit. Once you have that function working, place a call to it in the Fibonacci function— replacing your “print b” statement. Like this:
(1) def fin(n):
(2) a, b = 0, 1
(3) while b < n:
(4) if is_prime(b): print b # is_prime checks for prime
(5) a,b = b, b+1
The is_prime function receives an integer argument, and tests to see if the argument a prime number. It would basically be the inner loop of your prime number generator above. Have is_prime return either True or False.
Hope this helps.
Hi. I have created articles on prime numbers here:
http://math4allages.wordpress.com/2010/06/14/prime-series-1/
http://math4allages.wordpress.com/2010/06/21/prime-series-2/
You may want to check it out.
that was simple at all. There are other methods I have seen on google to write primes in python and yours was wayyyy too long.
while(trial_divisor**2 guaranteed not a prime.
Still, it won’t be the fastest way using integers (binary solutions are way faster) and starting the divisor at 2 every loop is also wasted (using an array / list with found primes is also upping the performance by a factor about 8, if the number is not a prime, you don’t need it as a divisor).
But i guess as an example the most comprehendible.
** half of my message got cut?? **
while(trial_divisor**2 guaranteed not a prime.
Still, it won’t be the fastest way using integers (binary solutions are way faster) and starting the divisor at 2 every loop is also wasted (using an array / list with found primes is also upping the performance by a factor about 8, if the number is not a prime, you don’t need it as a divisor).
But i guess as an example the most comprehendible.
** missing part … ? **
sorry, but this part is just not right.
Why are you making a square of every divisor in a loop?
Get the square root of the candidate and save it in a temporary variable and check against it. You’ll save 1*n – 1 calculation…
And as Rob Allison demonstrated, you don’t need to use divisor++ in the loop, since every second divisor would be divisible by 2 in this solution => guaranteed not a prime.
This code wasn’t offered as a fast example of finding prime numbers, just one that does what it claims to do. That’s why the comment reads “works by brute force . . . not very fast.”