University of Calgary

playing with primes

Playing with Primes
source: Katrin Becker, 2001
Some people find prime numbers fascinating. Indeed, they do seem to possess a number of interesting properties. What follows is a series of properties, conjectures and the like that have to do with prime numbers. Your task is to choose any 2 (two) and implement them.
With a careful design and a bit of planning it may be possible to do both in the same program. At the very least, even if you end up writing two separate programs, there will be some overlap - code that can be used in both programs.
Although the use of procedures is probably helpful in this situation, you are NOT required to use them for this assignment.
Note: The Sieve of Eratosthenes may not be the best algorithm to use to find prime numbers.
Recall:
A prime number is one that can only be evenly divided by one and itself. [Is 1 prime?] A number may checked for "primeness" by trying to find all it's factor. You may make use of the factors program(s) if you wish. Remember to credit your sources.
ONE: Goldbach's Conjecture:
Every even number > 2 can be written as the sum of two primes:
E.g.
4 = 2 + 2
8 = 3 + 5
16 = 11 + 5
Write a program that determines for every even integer N with 2 <= N <= 200 two prime numbers P and Q such that N = P + Q;
TWO: Prime Twins:
If a study is made of a list of prime numbers for any length of time, certain features soon become evident. One of them is the occurrence of "prime twins". These are prime numbers that differ by two. For example 3 and 5; 5 and 7; 11 and 13; 17 and 19, etc. It has been speculated that there are only a finite number of these prime twins; however it has never been proven one way or another.
Write a program to generate all prime twins less than 2000.
THREE: Permutable Primes:
Some prime numbers have been found that remain prime for all possible permutations of the digits contained within the number. For example 13 and 31 are both prime. So are 113, 131, and 311.
Write a program to generate all permutable primes less than 2000.
FOUR: Power Primes (not their real name):
There are a large number of primes of the form NN+1. For example: 22+1= 5.
Write a program to determine whether NN+1 is prime, given 1 <= N <= 10. NOTE: 1010 cannot be represented using ordinary integers.
FIVE: Factorial Primes (not their real name):
Some prime numbers may be expressed in the form N! + 1. In fact it has been conjectured that there exists infinitely many prime numbers of this form. For example: 2!+1=3; 3!+1 = 1*2*3+1 = 6+1 = 7, but 4!+1 is not prime.
Write a program to find which primes (< 2000) may be expressed as N! + 1.
SIX: Switching Digits:
Given an integer N it is sometimes possible to forma a prime number by changing just one of its digits. For example: by changing 8 to 9 in 18 we have a prime number. Changing 2 to 3 in 423 also gives us a prime.
Write a program to find the smallest number that can NOT be made into a prime by changing one of its digits.
SEVEN: Mersenne Primes:
In the first half of the seventeenth century Father Martin Mersenne conjectured that the prime numbers of the form 2p-1 are prime whenever the number P is prime. These quickly became known as "Mersenne Primes" and they are denoted by M P . The number M127 = 2127-1 held the record for the largest known prime number and even in 1950 an attempt to find a larger one failed. [ As of 1972 the largest known prime was a Mersenne prime: 211213-1, a number with 3376 decimal digits.] Unfortunately, Father Mersenne's conjecture has not held up and there are several examples of M P
that are not primes.
Write a program to determine which values of P less than 20 (P always a prime number) result in MP being prime.
Source for the preceding problems: Maurer, H.A. and M.R.Williams, "A Collection of Programming Problems and Techniques", 1972, Prentice-Hall
The program must be fully documented and follow appropriate style constraints. You must provide sufficient evidence that the program compiles and executes correctly.
Notes on Marking:
In order to pass it must work. (Some marks will be given to all *reasonable* attempts, working or not)
For a Maximum Grade of C+:

For a Maximum Grade of B+:

For a Maximum Grade of A:

Important Note: if your program does not function properly it is possible to verify that some parts work if you have produced a reasonable trace (see sample solution)
BONUS:
1. Include a short discussion (1/2 page?) of how number representation in a computer causes problems when working with very large numbers and sugeest at least one approach to dealing with it.
2. For each additional problem solved. (i.e. Implement three or more).
CHALLENGE:
Implement your solution for arbitrarily large (> 231) numbers.



Updated: August 9, 2005 10:23 PM