created 06/30/2018

Chapter 31 Programming Exercises

Exercise 1 — Prime Numbers

A prime number is an integer 2 or greater that not a multiple of any smaller integer (other than 1). Prime numbers are extremely important in cryptography and computer security. (See Chapter 86 exercises for more in prime numbers.)

For example, 13 is a prime number because it is not a multiple of any of the integers 2 through 12. Another way of saying this is 13 mod m is not zero for m from 2 to 12.

An integer that is not prime is composite. It is the product of at least two other integers.

For example, 12 is composite because it is the product of 3 and 4.

Write a program that asks the user for an integer N and then writes out if it is prime or composite. If N is one, it is not prime (by definition.) If N is two, it is prime (by definition.) Now check if N is even. If N is even and greater than two, then it is divisible by two, and not prime. Then try to divide N by odd trial divisors Tfrom 3 up to square root of N. Rather than computing the square root (which is expensive), end the search when T*T == N.

C:\>java PrimeTest
Enter N: 223
223 is prime
C:\>

Exercise 2 — Prime Numbers between two Limits

C:\>java PrimeSearch
Enter low  limit: 1
Enter high limit: 50
Prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
31, 37, 41, 43, 47, 53, 59, 61, 67, 
71, 73, 79, 83, 89, 97
C:\>

Exercise 3 — Bertrand's Postulate

Bertrand's Postulate is that for N > 1 there is at least one prime greater than N and less than 2N.

Ask the user for N and check that there is at least one prime p in the range N < p < 2N.

C:\>java Bertrand
Enter N: 10
Prime numbers between 10 and 20 are:
11, 13, 17, 19 
C:\>

Exercise 4 — Twin Primes

Other than 2 and 3, no two primes can be consecutive. But sometimes there are pairs of primes such as 17 and 19 that differ by only two. These are called twin primes. Other examples are (3 and 5), (5 and 7), (11 and 13).

Write a program that asks the user for N and then writes out the twin primes from 2 to N.

C:\>java TwinPrimes
Enter N: 100
Twin Primes:
3, 5
5, 7
11, 13
17, 19
29, 31
41, 43
59, 61
71, 73 
C:\>

It is not known if there are infinitely many twin primes.

End of the Exercises