5.1 Primes
Determine whether a given integer number is prime.
5.1.1 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5:
6: System.out.println(isPrime(7));
7: }
8:
9: boolean isPrime(int a)
10: {
11: //Special cases
12: if(a==1) return false;
13: if(a==2) return true;
14:
15: boolean prime = true;
16: int count = 2;
17:
18: do
19: {
20: if (a%count==0)
21: {
22: prime = false;
23: }
24: count++;
25: } while(prime == true && count*count <=a);
26:
27: return prime;
28: }
29:
30: public static void main(String[] args)
31: {
32: new NNArithmetic();
33: }
34: }
35:
5.2 GCD
Use Euclid’s Algorithm to determine the Greatest Common Divisor of two positive integer numbers
5.2.1 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5:
6: System.out.println(gcd (1071, 462));
7: System.out.println(gcd (6, 35));
8: System.out.println(gcd (36, 63));
9: }
10:
11:
12: int gcd(int a, int b)
13: {
14: if(b>a) //Make sure the first number is largest
15: {
16: int temp = a;
17: a = b;
18: b = temp;
19: }
20:
21: while(b>0)
22: {
23: int remainder = a%b;
24: a = b;
25: b = remainder;
26: }
27:
28: return a;
29: }
30:
31: public static void main(String[] args)
32: {
33: new NNArithmetic();
34: }
35: }
36:
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 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5: System.out.println(isCoprime(35,64));
6: }
7:
8: int gcd(int a, int b)
9: {
10: if(b>a) //Make sure the first number is largest
11: {
12: int temp = a;
13: a = b;
14: b = temp;
15: }
16:
17: while(b>0)
18: {
19: int remainder = a%b;
20: a = b;
21: b = remainder;
22: }
23:
24: return a;
25: }
26:
27:
28: boolean isCoprime(int a, int b)
29: {
30: return (gcd(a,b) ==1) ? true : false;
31: }
32:
33: public static void main(String[] args)
34: {
35: new NNArithmetic();
36: }
37: }
38:
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.
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 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5: System.out.println(phi(10));
6: }
7:
8: int gcd(int a, int b)
9: {
10: if(b>a) //Make sure the first number is largest
11: {
12: int temp = a;
13: a = b;
14: b = temp;
15: }
16:
17: while(b>0)
18: {
19: int remainder = a%b;
20: a = b;
21: b = remainder;
22: }
23:
24: return a;
25: }
26:
27: boolean isCoprime(int a, int b)
28: {
29: return (gcd(a,b) ==1) ? true : false;
30: }
31:
32: int phi(int m)
33: {
34: if (m==1) return 1; //Special Case
35:
36: int phi = 0;
37: for(int i = 1; i<m; i++)
38: {
39: if (isCoprime(m,i)) phi++;
40: }
41: return phi;
42: }
43:
44: public static void main(String[] args)
45: {
46: new NNArithmetic();
47: }
48: }
49:
5.5 Prime Factors
Write a method that prints the prime factors of a given positive integer
5.5.1 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5: printPrimeFactors(315);
6: printPrimeFactors(98);
7: }
8:
9: void printPrimeFactors(int n)
10: {
11: for(int i = 2; i*i<=n; i++)
12: {
13: while(n%i == 0)
14: {
15: System.out.print(i + " ");
16: n = n/i;
17: }
18: }
19: if(n>1) System.out.print(n + "\n");
20: else System.out.println("");
21: }
22:
23: public static void main(String[] args)
24: {
25: new NNArithmetic();
26: }
27: }
28:
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 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5: printPrimesInRange(10,20);
6: }
7:
8: boolean isPrime(int a)
9: {
10: //Special cases
11: if(a==1) return false;
12: if(a==2) return true;
13:
14: boolean prime = true;
15: int count = 2;
16:
17: do
18: {
19: if (a%count==0)
20: {
21: prime = false;
22: }
23: count++;
24: } while(prime == true && count*count <=a);
25:
26: return prime;
27: }
28: void printPrimesInRange(int a , int b)
29: {
30: for (int i = a; i<=b; i++)
31: {
32: if (isPrime(i)) System.out.print(i + " ");
33: }
34: System.out.println("");
35: }
36: public static void main(String[] args)
37: {
38: new NNArithmetic();
39: }
40: }
41:
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 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5: printGoldbachPair(28);
6: printGoldbachPair(1856);
7: }
8:
9: boolean isPrime(int a)
10: {
11: //Special cases
12: if(a==1) return false;
13: if(a==2) return true;
14:
15: boolean prime = true;
16: int count = 2;
17:
18: do
19: {
20: if (a%count==0)
21: {
22: prime = false;
23: }
24: count++;
25: } while(prime == true && count*count <=a);
26:
27: return prime;
28: }
29: int [] goldbachPair(int n)
30: {
31: int count = 2;
32: int [] pair = new int[2];
33: boolean foundPair = false;
34: while(foundPair == false && count <= n/2)
35: {
36: if(isPrime(count) && isPrime(n-count))
37: {
38: foundPair = true;
39: pair [0] = count;
40: pair [1] = (n-count);
41: }
42: count++;
43: }
44: return pair;
45: }
46:
47: void printGoldbachPair(int n)
48: {
49: int [] pair = goldbachPair(n);
50: System.out.println(pair[0] + " + " + pair [1] + " = " + n);
51: }
52:
53:
54: public static void main(String[] args)
55: {
56: new NNArithmetic();
57: }
58: }
59:
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.
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 Solution
1: public class NNArithmetic {
2:
3: NNArithmetic()
4: {
5: printGoldbachList(9, 20);
6: printGoldbachList(1,2000,50);
7: }
8:
9: boolean isPrime(int a)
10: {
11: //Special cases
12: if(a==1) return false;
13: if(a==2) return true;
14:
15: boolean prime = true;
16: int count = 2;
17:
18: do
19: {
20: if (a%count==0)
21: {
22: prime = false;
23: }
24: count++;
25: } while(prime == true && count*count <=a);
26:
27: return prime;
28: }
29: int [] goldbachPair(int n)
30: {
31: int count = 2;
32: int [] pair = new int[2];
33: boolean foundPair = false;
34: while(foundPair == false && count <= n/2)
35: {
36: if(isPrime(count) && isPrime(n-count))
37: {
38: foundPair = true;
39: pair [0] = count;
40: pair [1] = (n-count);
41: }
42: count++;
43: }
44: return pair;
45: }
46:
47: void printGoldbachPair(int n)
48: {
49: int [] pair = goldbachPair(n);
50: System.out.println(pair[0] + " + " + pair [1] + " = " + n);
51: }
52:
53: void printGoldbachList(int a, int b)
54: {
55: if(a%2==1) a++; // make sure start on even number
56: for (int i = a ; i<=b ; i+=2)
57: {
58: printGoldbachPair(i);
59: }
60:
61: }
62:
63: void printGoldbachList(int a, int b, int min)
64: {
65: if(a%2==1) a++; // make sure start on even number
66: for (int i = a ; i<=b ; i+=2)
67: {
68: int [] pair = goldbachPair(i);
69: if(pair[0] > min && pair[1] > min) printGoldbachPair(i);
70: }
71: }
72:
73: public static void main(String[] args)
74: {
75: new NNArithmetic();
76: }
77: }
Tony Ballantyne Tech 