These are optional exercises for practicing the concepts we learned this week.
The largest known prime number is currently
282,589,933 − 1
How many digits does this number have, approximately?
Write a program that reads an integer n and prints the nth prime number.
Bertrand's postulate, first proven in 1852, states that for every integer n > 1 there is at least one prime p such that
n < p < 2n
Write a program that reads an integer n > 1 and prints the count of prime numbers p in the range n < p < 2n. Also print the percentage of the numbers in this range that are prime. For example:
Enter n: 5 1 prime number(s) in the range 5 < x < 10 25.0 % are prime
Explanation: There are four numbers (6, 7, 8, 9) in that range. Only one (7) is prime. 1 / 4 = 25%.
Write a program that reads an integer N and prints a text plot of the integers 0 through (N – 1). Each output line should represent 50 integers, and should display a P for a prime number or a '.' for a number that is not prime.
For example, if N = 100 then the program will print
0 : ..PP.P.P...P.P...P.P...P.....P.P.....P...P.P...P.. 50 : ...P.....P.P.....P...P.P.....P...P.....P.......P..
The first row represents the integers 0 through 49. The first two characters in that row are '.', because 0 and 1 are not prime. The next two characters are 'P', because 2 and 3 are prime. The next character is '.', because 4 is not prime, and so on. SImilarly, the next row represents the integers 50 through 99.
Run your program for a large value of N, such as N = 1,000,000. As the output progresses, you will see that primes gradually become less common.
Write a program that reads an integer n and prints its largest prime factor.
Write a program that reads an integer n and prints its prime factor that occurs the most times in n's prime factorization. (If more than one prime factor has a maximum number of occurrences, print the largest such factor.)
An integer is square free if every prime in its prime factorization appears exactly once. For example, 42 is square free because 42 = 2 ⋅ 3 ⋅ 7, and no primes are repeated in that list. 18 is not square free, because 18 = 2 ⋅ 3 ⋅ 3, and the prime 3 appears twice in the factorization.
Write a program that reads an integer N, and prints "square free" if it is square free, otherwise "not square free".
Write a program to determine how many 3-digit primes exist that have only odd digits.
The Fermat number F7 has 39 digits. It is
F7 = 2128 + 1 = 340,282,366,920,938,463,463,374,607,431,768,211,457
It was first factored in 1970:
F7 = 59,649,589,127,497,217 (17 digits) × 5,704,689,200,685,129,054,721 (22 digits)
Suppose that our implementation of integer factorization via trial division can test 1 billion potential divisors per second. Approximately how long would it take to factor F7?
Write a program that reads integers a and b, and prints the fraction a / b in unsimplified and simplified form. To simplify the fraction, divide by the greatest common divisor of a and b. For example:
Enter a: 12 Enter b: 20 12 / 20 = 3 / 5
Two integers a and b are relatively prime (or coprime) if they have no prime factors in common, i.e. if gcd(a, b) = 1.
What is the probability that two random integers will be relatively prime? To investigate this question, write a program that reads an integer N and chooses 100,000 random pairs of integers a, b with 2 ≤ a, b ≤ N. Print the fraction of these pairs that are relatively prime.
Try running your program with various values of N. As N gets larger, the output fraction should converge toward some value. What is it, approximately?