SHOW:
|
|
- or go back to the newest paste.
1 | package Euler; | |
2 | ||
3 | import java.util.ArrayList; | |
4 | package Euler; | |
5 | ||
6 | import java.util.ArrayList; | |
7 | public class p046 { | |
8 | public static void main(String[] args){ | |
9 | int compositeList[] = Euler.listOddComposites(10000); | |
10 | for(int i:compositeList){ | |
11 | if(checkGoldbach(i)==false){ | |
12 | System.out.println(i+" is the smallest counterexample to Goldbach's conjecture."); | |
13 | break; | |
14 | } | |
15 | } | |
16 | ||
17 | } | |
18 | public static boolean checkGoldbach(int i){ | |
19 | int primeList[]=Euler.listPrimes(10000); | |
20 | ArrayList<Boolean> goldbach=new ArrayList<Boolean>(); | |
21 | for(int j=0;primeList[j]<i&!goldbach.contains(true);j++){ | |
22 | if((Math.sqrt((i-primeList[j])/2))%1==0){ | |
23 | System.out.println(i+"="+primeList[j]"+2*"+(int)Math.sqrt((i-primeList[j])/2)+"^2"); | |
24 | - | System.out.println(i+"="+j+"+2*"+(int)Math.sqrt((i-primeList[j])/2)+"^2"); |
24 | + | |
25 | } | |
26 | } | |
27 | if(goldbach.contains(true)) | |
28 | return true; | |
29 | else | |
30 | return false; | |
31 | } | |
32 | } | |
33 | ||
34 | ||
35 | ODD COMPOSITES SIEVE. | |
36 | ||
37 | public static int[] listOddComposites(int n) { | |
38 | boolean[] isprime = listPrimality(n); | |
39 | int count = 0; | |
40 | for (boolean b : isprime) { | |
41 | if (!b) | |
42 | count++; | |
43 | } | |
44 | int[] result = new int[count]; | |
45 | for (int i = 4, j = 0; i < isprime.length; i++) { | |
46 | if (!isprime[i]&&i%2!=0) { | |
47 | result[j] = i; | |
48 | j++; | |
49 | } | |
50 | } | |
51 | int c=1,i=0; | |
52 | for(i=0;c!=0;i++){ | |
53 | if(result[i]==0){ | |
54 | c=0; | |
55 | } | |
56 | } | |
57 | int[] finalListTrim = new int[i-1]; | |
58 | for(int j=0;j<i-1;j++){ | |
59 | finalListTrim[j]=result[j]; | |
60 | } | |
61 | return finalListTrim; | |
62 | } | |
63 | public static boolean[] listPrimality(int n) { | |
64 | boolean[] result = new boolean[n+1]; | |
65 | if (n >= 2) | |
66 | result[2] = true; | |
67 | for (int i = 3; i <= n; i += 2) | |
68 | result[i] = true; | |
69 | for (int i = 3, end = (int)Math.sqrt(n); i <= end; i += 2) { | |
70 | if (result[i]) { | |
71 | for (int j = i * i; j <= n; j += i << 1) | |
72 | result[j] = false; | |
73 | } | |
74 | } | |
75 | return result; | |
76 | } |