Goldbach’s conjecture (java)

Question

I need to print out Goldbach’s conjecture for the first 1000 elements (in the code you'll notice I am only working with 100 elements for simplicity and that I am including 1 as a prime). I understand that Goldbach’s conjecture says that every even number can be expressed as a sum of two primes. My program works, but it's skipping certain even numbers such as 8, 12, etc, and I'm unsure how to fix this. Please help me figure this out.

public class GoldbachClass {
public static void main(String[] args) {
    // TODO Auto-generated method stub

    int i;
    int num = 0;
    int maxCheck = 100; // limit set to which you want to find prime numbers
    boolean isPrime = true;

    int[] primeNumbers = new int [maxCheck];

    //Start loop 1 to maxCheck
    for (i = 1; i <= maxCheck; i++) 
    {
        isPrime = CheckPrime(i);
        if (isPrime) 
        {
            primeNumbers[i] = i;
        }
    }

    System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
    // Print prime numbers from 1 to maxCheck
    for (int j = 1; j < primeNumbers.length; j++)
    {
        if (primeNumbers[j] != 0){
        System.out.printf("%d ", primeNumbers[j]);
        }
    }
    System.out.println();

    for (int j = 1; j < primeNumbers.length; j++)
    {
        if (primeNumbers[j] != 0)
        {
            num = primeNumbers[j] + primeNumbers[j];
        System.out.printf("%d = %d + %d\n", num, primeNumbers[j], primeNumbers[j]);
        }
    }
}

public static boolean CheckPrime(int numberToCheck) {
    int remainder;
    for (int i = 2; i <= numberToCheck / 2; i++) {
        remainder = numberToCheck % i;
        //if remainder is 0 than numberToCheckber is not prime and break loop. Elese continue loop
        if (remainder == 0) {
            return false;
        }
    }
    return true;
}  
}

Answer 1

Goldbach's Conjecture is that an even number can be restated as the sum of two primes. Not that any prime times two is even. I used a few optimizations. I was not sure if you wanted all of the pairs of primes or just the first hit. If you want them all just remove the continue and break statements I have labeled. You may want to read up on 6k±1 and primes > 4. I tested up to 100,000 and it took about a second. With the break commented out 100k takes a few minutes.

public class GoldbachClass {

    public static void main(String[] args) {
        int maxCheck = 100;
        int k,num;
        // Goldbach check for evens from 1 to maxCheck
        for (num = 4; num <= maxCheck; num+=2) { // just evens to check
            if (num%2==1) continue; // just evens 
            for (k=2; k<=(int)num/2+1; k++) { // just until num/2
                if (CheckPrime(num-k) && CheckPrime(k)) {
                    System.out.printf("%d = %d + %d\n", num, num-k, k);
                    //break; // remove for all pairs
                } 
            }
        }
    }

 public static boolean CheckPrime(int numberToCheck) {
    int remainder = numberToCheck%6; // for 6k check 
    if (numberToCheck <=3) return (numberToCheck>1);
    if (remainder!=1 && remainder!=5) return false; // not 6k±1
    int limit = (int)Math.sqrt(numberToCheck)+1;
    for (int i = 5; i <= limit; i+=6) { // just check 6k±1
        if (numberToCheck%i==0 || numberToCheck%(i+2)==0) return false;
    }
    return true;
    }  
}

Output:

 $ time java GoldbachClass 
4 = 2 + 2
6 = 3 + 3
8 = 5 + 3
8 = 3 + 5
10 = 7 + 3
10 = 5 + 5
12 = 7 + 5
12 = 5 + 7
14 = 11 + 3
14 = 7 + 7
16 = 13 + 3
16 = 11 + 5
18 = 13 + 5
18 = 11 + 7
20 = 17 + 3
20 = 13 + 7
22 = 19 + 3
22 = 17 + 5
22 = 11 + 11
24 = 19 + 5
24 = 17 + 7
24 = 13 + 11
24 = 11 + 13
26 = 23 + 3
26 = 19 + 7
26 = 13 + 13
28 = 23 + 5
28 = 17 + 11
30 = 23 + 7
30 = 19 + 11
30 = 17 + 13
32 = 29 + 3
32 = 19 + 13
34 = 31 + 3
34 = 29 + 5
34 = 23 + 11
34 = 17 + 17
36 = 31 + 5
36 = 29 + 7
36 = 23 + 13
36 = 19 + 17
36 = 17 + 19
38 = 31 + 7
38 = 19 + 19
40 = 37 + 3
40 = 29 + 11
40 = 23 + 17
42 = 37 + 5
42 = 31 + 11
42 = 29 + 13
42 = 23 + 19
44 = 41 + 3
44 = 37 + 7
44 = 31 + 13
46 = 43 + 3
46 = 41 + 5
46 = 29 + 17
46 = 23 + 23
48 = 43 + 5
48 = 41 + 7
48 = 37 + 11
48 = 31 + 17
48 = 29 + 19
50 = 47 + 3
50 = 43 + 7
50 = 37 + 13
50 = 31 + 19
52 = 47 + 5
52 = 41 + 11
52 = 29 + 23
54 = 47 + 7
54 = 43 + 11
54 = 41 + 13
54 = 37 + 17
54 = 31 + 23
56 = 53 + 3
56 = 43 + 13
56 = 37 + 19
58 = 53 + 5
58 = 47 + 11
58 = 41 + 17
58 = 29 + 29
60 = 53 + 7
60 = 47 + 13
60 = 43 + 17
60 = 41 + 19
60 = 37 + 23
60 = 31 + 29
60 = 29 + 31
62 = 59 + 3
62 = 43 + 19
62 = 31 + 31
64 = 61 + 3
64 = 59 + 5
64 = 53 + 11
64 = 47 + 17
64 = 41 + 23
66 = 61 + 5
66 = 59 + 7
66 = 53 + 13
66 = 47 + 19
66 = 43 + 23
66 = 37 + 29
68 = 61 + 7
68 = 37 + 31
70 = 67 + 3
70 = 59 + 11
70 = 53 + 17
70 = 47 + 23
70 = 41 + 29
72 = 67 + 5
72 = 61 + 11
72 = 59 + 13
72 = 53 + 19
72 = 43 + 29
72 = 41 + 31
74 = 71 + 3
74 = 67 + 7
74 = 61 + 13
74 = 43 + 31
74 = 37 + 37
76 = 73 + 3
76 = 71 + 5
76 = 59 + 17
76 = 53 + 23
76 = 47 + 29
78 = 73 + 5
78 = 71 + 7
78 = 67 + 11
78 = 61 + 17
78 = 59 + 19
78 = 47 + 31
78 = 41 + 37
80 = 73 + 7
80 = 67 + 13
80 = 61 + 19
80 = 43 + 37
82 = 79 + 3
82 = 71 + 11
82 = 59 + 23
82 = 53 + 29
82 = 41 + 41
84 = 79 + 5
84 = 73 + 11
84 = 71 + 13
84 = 67 + 17
84 = 61 + 23
84 = 53 + 31
84 = 47 + 37
84 = 43 + 41
84 = 41 + 43
86 = 83 + 3
86 = 79 + 7
86 = 73 + 13
86 = 67 + 19
86 = 43 + 43
88 = 83 + 5
88 = 71 + 17
88 = 59 + 29
88 = 47 + 41
90 = 83 + 7
90 = 79 + 11
90 = 73 + 17
90 = 71 + 19
90 = 67 + 23
90 = 61 + 29
90 = 59 + 31
90 = 53 + 37
90 = 47 + 43
92 = 89 + 3
92 = 79 + 13
92 = 73 + 19
92 = 61 + 31
94 = 89 + 5
94 = 83 + 11
94 = 71 + 23
94 = 53 + 41
94 = 47 + 47
96 = 89 + 7
96 = 83 + 13
96 = 79 + 17
96 = 73 + 23
96 = 67 + 29
96 = 59 + 37
96 = 53 + 43
98 = 79 + 19
98 = 67 + 31
98 = 61 + 37
100 = 97 + 3
100 = 89 + 11
100 = 83 + 17
100 = 71 + 29
100 = 59 + 41
100 = 53 + 47

real    0m0.097s
user    0m0.129s
sys     0m0.037s

Here is how I would do it:

public class GoldbachClass {

    public static void main(String[] args) {
        int maxCheck = 100;
        int num,a;      
        // Goldbach check for evens from 4 to maxCheck
        for (num = 4; num <= maxCheck; num++) { // just evens to check
            goldbach(num);
        }
    }
    
    public static void goldbach(int N) {
        int p = 2;
        if (N == 5 || N < 4) return;
        System.out.printf("%d = ",N);
        if (N%2==1 && N > 5) {
            System.out.printf("3 + "); // Goldbach Weak 
            N-=3;
        }
        while (!CheckPrime(N-p))  // find Goldbach prime
            p = nextPrime(p);
        System.out.printf("%d + %d\n",p, N-p);
        return; // OK because no int less tha 2**35 has been found to fail
    }
    
    public static int nextPrime(int p) {
        while(!CheckPrime(++p)) {} // next prime number
        return p;
    }

    public static boolean CheckPrime(int numberToCheck) {
        if (numberToCheck <=3) return (numberToCheck>1);
        int remainder = numberToCheck%6; // for 6k check 
        if (remainder!=1 && remainder!=5) return false; // not 6k±1
        int limit = (int)Math.sqrt(numberToCheck)+1;
        for (int i = 5; i <= limit+1; i+=6)  // just check 6k±1
            if (numberToCheck%i==0 || numberToCheck%(i+2)==0) return false;
        return true;
        }  
}

This does both even and odd numbers for the Strong and Weak Conjectures.

$ time java GoldbachClass 
4 = 2 + 2
6 = 3 + 3
7 = 3 + 2 + 2
8 = 3 + 5
9 = 3 + 3 + 3
10 = 3 + 7
11 = 3 + 3 + 5
12 = 5 + 7
13 = 3 + 3 + 7
14 = 3 + 11
15 = 3 + 5 + 7
16 = 3 + 13
17 = 3 + 3 + 11
18 = 5 + 13
19 = 3 + 3 + 13
20 = 3 + 17
21 = 3 + 5 + 13
22 = 3 + 19
23 = 3 + 3 + 17
24 = 5 + 19
25 = 3 + 3 + 19
26 = 3 + 23
27 = 3 + 5 + 19
28 = 5 + 23
29 = 3 + 3 + 23
30 = 7 + 23
31 = 3 + 5 + 23
32 = 3 + 29
33 = 3 + 7 + 23
34 = 3 + 31
35 = 3 + 3 + 29
36 = 5 + 31
37 = 3 + 3 + 31
38 = 7 + 31
39 = 3 + 5 + 31
40 = 3 + 37
41 = 3 + 7 + 31
42 = 5 + 37
43 = 3 + 3 + 37
44 = 3 + 41
45 = 3 + 5 + 37
46 = 3 + 43
47 = 3 + 3 + 41
48 = 5 + 43
49 = 3 + 3 + 43
50 = 3 + 47
51 = 3 + 5 + 43
52 = 5 + 47
53 = 3 + 3 + 47
54 = 7 + 47
55 = 3 + 5 + 47
56 = 3 + 53
57 = 3 + 7 + 47
58 = 5 + 53
59 = 3 + 3 + 53
60 = 7 + 53
61 = 3 + 5 + 53
62 = 3 + 59
63 = 3 + 7 + 53
64 = 3 + 61
65 = 3 + 3 + 59
66 = 5 + 61
67 = 3 + 3 + 61
68 = 7 + 61
69 = 3 + 5 + 61
70 = 3 + 67
71 = 3 + 7 + 61
72 = 5 + 67
73 = 3 + 3 + 67
74 = 3 + 71
75 = 3 + 5 + 67
76 = 3 + 73
77 = 3 + 3 + 71
78 = 5 + 73
79 = 3 + 3 + 73
80 = 7 + 73
81 = 3 + 5 + 73
82 = 3 + 79
83 = 3 + 7 + 73
84 = 5 + 79
85 = 3 + 3 + 79
86 = 3 + 83
87 = 3 + 5 + 79
88 = 5 + 83
89 = 3 + 3 + 83
90 = 7 + 83
91 = 3 + 5 + 83
92 = 3 + 89
93 = 3 + 7 + 83
94 = 5 + 89
95 = 3 + 3 + 89
96 = 7 + 89
97 = 3 + 5 + 89
98 = 19 + 79
99 = 3 + 7 + 89
100 = 3 + 97

real    0m0.090s
user    0m0.122s
sys     0m0.019s

Answer 2

Let's address some specific problems with your code: Goldbach's conjecture only applies to even numbers, but your code outputs odd numbers too, so we'll filter for even results; your prime test checks up to numberToCheck/2 instead of the square root of numberToCheck; your final production loop really needs to be a pair of nested loops:

public class GoldbachClass {

    public static void main(String[] args) {

        int maxCheck = 100;

        int[] primeNumbers = new int[maxCheck];

        for (int number = 1, index = 0; number <= maxCheck; number++, index++) {
            if (isPrime(number)) {
                primeNumbers[index] = number;
            }
        }

        System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
        for (int index = 0; index < primeNumbers.length; index++) {
            if (primeNumbers[index] != 0) {
                System.out.printf("%d ", primeNumbers[index]);
            }
        }

        System.out.println();

        for (int i = 0; i < primeNumbers.length; i++) {
            if (primeNumbers[i] == 0) {
                continue;
            }

            for (int j = i; j < primeNumbers.length; j++) {
                if (primeNumbers[j] == 0) {
                    continue;
                }

                int number = primeNumbers[i] + primeNumbers[j];

                if (number % 2 == 0) { // conjecture only applies to even numbers
                    System.out.printf("%d = %d + %d\n", number, primeNumbers[i], primeNumbers[j]);
                }
            }
        }
    }

    public static boolean isPrime(int number) {

        if (number < 2 || number % 2 == 0) {
            return (number == 2);
        }

        for (int odd = 3; odd * odd <= number; odd += 2) {
            if (number % odd == 0) {
                return false;
            }
        }

        return true;
    }
}

Output filtered through Unix sort:

% java GoldbachClass | sort -n
Prime numbers from 1 to 100 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 
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7
10 = 5 + 5
12 = 5 + 7
14 = 3 + 11
14 = 7 + 7
16 = 3 + 13
16 = 5 + 11
18 = 5 + 13
18 = 7 + 11
20 = 3 + 17
20 = 7 + 13
22 = 11 + 11
22 = 3 + 19
22 = 5 + 17
24 = 11 + 13
24 = 5 + 19
24 = 7 + 17
26 = 13 + 13
26 = 3 + 23
26 = 7 + 19
28 = 11 + 17
28 = 5 + 23
30 = 11 + 19
30 = 13 + 17
30 = 7 + 23
32 = 13 + 19
32 = 3 + 29
34 = 11 + 23
34 = 17 + 17
34 = 3 + 31
34 = 5 + 29
36 = 13 + 23
36 = 17 + 19
36 = 5 + 31
36 = 7 + 29
38 = 19 + 19
38 = 7 + 31
40 = 11 + 29
40 = 17 + 23
40 = 3 + 37
42 = 11 + 31
42 = 13 + 29
42 = 19 + 23
42 = 5 + 37
44 = 13 + 31
44 = 3 + 41
44 = 7 + 37
46 = 17 + 29
46 = 23 + 23
46 = 3 + 43
46 = 5 + 41
48 = 11 + 37
48 = 17 + 31
48 = 19 + 29
48 = 5 + 43
48 = 7 + 41
50 = 13 + 37
50 = 19 + 31
50 = 3 + 47
50 = 7 + 43
52 = 11 + 41
52 = 23 + 29
52 = 5 + 47
54 = 11 + 43
54 = 13 + 41
54 = 17 + 37
54 = 23 + 31
54 = 7 + 47
56 = 13 + 43
56 = 19 + 37
56 = 3 + 53
58 = 11 + 47
58 = 17 + 41
58 = 29 + 29
58 = 5 + 53
60 = 13 + 47
60 = 17 + 43
60 = 19 + 41
60 = 23 + 37
60 = 29 + 31
60 = 7 + 53
62 = 19 + 43
62 = 3 + 59
62 = 31 + 31
64 = 11 + 53
64 = 17 + 47
64 = 23 + 41
64 = 3 + 61
64 = 5 + 59
66 = 13 + 53
66 = 19 + 47
66 = 23 + 43
66 = 29 + 37
66 = 5 + 61
66 = 7 + 59
68 = 31 + 37
68 = 7 + 61
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41
70 = 3 + 67
72 = 11 + 61
72 = 13 + 59
72 = 19 + 53
72 = 29 + 43
72 = 31 + 41
72 = 5 + 67
74 = 13 + 61
74 = 3 + 71
74 = 31 + 43
74 = 37 + 37
74 = 7 + 67
76 = 17 + 59
76 = 23 + 53
76 = 29 + 47
76 = 3 + 73
76 = 5 + 71
78 = 11 + 67
78 = 17 + 61
78 = 19 + 59
78 = 31 + 47
78 = 37 + 41
78 = 5 + 73
78 = 7 + 71
80 = 13 + 67
80 = 19 + 61
80 = 37 + 43
80 = 7 + 73
82 = 11 + 71
82 = 23 + 59
82 = 29 + 53
82 = 3 + 79
82 = 41 + 41
84 = 11 + 73
84 = 13 + 71
84 = 17 + 67
84 = 23 + 61
84 = 31 + 53
84 = 37 + 47
84 = 41 + 43
84 = 5 + 79
86 = 13 + 73
86 = 19 + 67
86 = 3 + 83
86 = 43 + 43
86 = 7 + 79
88 = 17 + 71
88 = 29 + 59
88 = 41 + 47
88 = 5 + 83
90 = 11 + 79
90 = 17 + 73
90 = 19 + 71
90 = 23 + 67
90 = 29 + 61
90 = 31 + 59
90 = 37 + 53
90 = 43 + 47
90 = 7 + 83
92 = 13 + 79
92 = 19 + 73
92 = 3 + 89
92 = 31 + 61
94 = 11 + 83
94 = 23 + 71
94 = 41 + 53
94 = 47 + 47
94 = 5 + 89
96 = 13 + 83
96 = 17 + 79
96 = 23 + 73
96 = 29 + 67
96 = 37 + 59
96 = 43 + 53
96 = 7 + 89
98 = 19 + 79
98 = 31 + 67
98 = 37 + 61
100 = 11 + 89
100 = 17 + 83
100 = 29 + 71
100 = 3 + 97
100 = 41 + 59
100 = 47 + 53
102 = 13 + 89
102 = 19 + 83
102 = 23 + 79
102 = 29 + 73
102 = 31 + 71
102 = 41 + 61
102 = 43 + 59
102 = 5 + 97
104 = 31 + 73
104 = 37 + 67
104 = 43 + 61
104 = 7 + 97
106 = 17 + 89
106 = 23 + 83
106 = 47 + 59
106 = 53 + 53
108 = 11 + 97
108 = 19 + 89
108 = 29 + 79
108 = 37 + 71
108 = 41 + 67
108 = 47 + 61
110 = 13 + 97
110 = 31 + 79
110 = 37 + 73
110 = 43 + 67
112 = 23 + 89
112 = 29 + 83
112 = 41 + 71
112 = 53 + 59
114 = 17 + 97
114 = 31 + 83
114 = 41 + 73
114 = 43 + 71
114 = 47 + 67
114 = 53 + 61
116 = 19 + 97
116 = 37 + 79
116 = 43 + 73
118 = 29 + 89
118 = 47 + 71
118 = 59 + 59
120 = 23 + 97
120 = 31 + 89
120 = 37 + 83
120 = 41 + 79
120 = 47 + 73
120 = 53 + 67
120 = 59 + 61
122 = 43 + 79
122 = 61 + 61
124 = 41 + 83
124 = 53 + 71
126 = 29 + 97
126 = 37 + 89
126 = 43 + 83
126 = 47 + 79
126 = 53 + 73
126 = 59 + 67
128 = 31 + 97
128 = 61 + 67
130 = 41 + 89
130 = 47 + 83
130 = 59 + 71
132 = 43 + 89
132 = 53 + 79
132 = 59 + 73
132 = 61 + 71
134 = 37 + 97
134 = 61 + 73
134 = 67 + 67
136 = 47 + 89
136 = 53 + 83
138 = 41 + 97
138 = 59 + 79
138 = 67 + 71
140 = 43 + 97
140 = 61 + 79
140 = 67 + 73
142 = 53 + 89
142 = 59 + 83
142 = 71 + 71
144 = 47 + 97
144 = 61 + 83
144 = 71 + 73
146 = 67 + 79
146 = 73 + 73
148 = 59 + 89
150 = 53 + 97
150 = 61 + 89
150 = 67 + 83
150 = 71 + 79
152 = 73 + 79
154 = 71 + 83
156 = 59 + 97
156 = 67 + 89
156 = 73 + 83
158 = 61 + 97
158 = 79 + 79
160 = 71 + 89
162 = 73 + 89
162 = 79 + 83
164 = 67 + 97
166 = 83 + 83
168 = 71 + 97
168 = 79 + 89
170 = 73 + 97
172 = 83 + 89
176 = 79 + 97
178 = 89 + 89
180 = 83 + 97
186 = 89 + 97
194 = 97 + 97
%

The results get ragged at the end due to our arbitrary prime cutoff maxCheck.