5.1 Primes
Determine whether a given integer number is prime.
5.1.1 Example
1: System.out.println(isPrime(7)); 2: *** Output *** 3: true
5.2 GCD
Use Euclid’s Algorithm to determine the Greatest Common Divisor of two positive integer numbers
5.2.1 Example
1: System.out.println(gcd (1071, 462)); 2: System.out.println(gcd (6, 35)); 3: System.out.println(gcd (36, 63)); 4: *** Output *** 5: 21 6: 1 7: 9
5.3 Coprimes
Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.
5.3.1 Example
1: System.out.println(isCoprime(35,64)); 2: *** Output *** 3: true
5.4 Totient Function
Calculate Euler’s totient function phi(m).
Euler’s so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.
For example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.
5.4.1 Example
1: System.out.println(phi(10)); 2: *** Output *** 3: 4
5.5 Prime Factors
Write a method that prints the prime factors of a given positive integer
5.5.1 Example
1: printPrimeFactors(315); 2: printPrimeFactors(98); 3: *** Output *** 4: 3 3 5 7 5: 2 7 7
5.6 List of Primes
Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.
5.6.1 Example
1: printPrimesInRange(10,20); 2: *** Output *** 3: 11 13 17 19
5.7 Goldbach’s Conjecture
Goldbach’s conjecture says that every positive even number greater than 2 is the sum of two prime numbers. Example: 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers.
Write a predicate to find the two prime numbers that sum up to a given even number.
5.7.1 Example
1: printGoldbachPair(28); 2: printGoldbachPair(1856); 3: *** Output *** 4: 5 + 23 = 28 5: 67 + 1789 = 1856
5.8 More Goldbach
Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition. In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50.
Try to find out how many such cases there are in the range 2..3000.
5.8.1 Example
1: printGoldbachList(9, 20); 2: printGoldbachList(1,2000,50); 3: *** Output *** 4: 3 + 7 = 10 5: 5 + 7 = 12 6: 3 + 11 = 14 7: 3 + 13 = 16 8: 5 + 13 = 18 9: 3 + 17 = 20 10: 73 + 919 = 992 11: 61 + 1321 = 1382 12: 67 + 1789 = 1856 13: 61 + 1867 = 1928
Tony Ballantyne Tech 