-
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Problem46.java
59 lines (48 loc) · 1.34 KB
/
Problem46.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
* File: Problem46.java
* ----------------------
* Finds the smallest odd composite that cannot be
* written as the sum of a prime and twice a square.
*
*/
import java.util.ArrayList;
public class Problem46 {
public static ArrayList<Integer> primes = new ArrayList<>();
public static void main(String[] args) {
// to calculate runtime of different methods
double startTime = System.nanoTime();
int number = 3; // Last demonstrated number on problem page
while (true) {
if (isPrime(number)) { // Stops the loop if the number isn't composite
primes.add(number);
} else {
if (provesGoldbachWrong(number)) {
System.out.println(number);
break;
}
}
number += 2; // Because it needs to be odd
}
double duration = (System.nanoTime() - startTime) / 1000000000;
System.out.println(duration + " seconds");
}
public static boolean isPrime(int number) {
for (int divisor = 2; divisor <= Math.sqrt(number); divisor++) {
if (number % divisor == 0) {
return false;
}
}
return true;
}
public static boolean provesGoldbachWrong(int number) {
// Condition because if the number is greater than nothing can add
for (int i = 1; 2 * i * i < number; i++) {
for (int prime : primes) {
if (number == prime + (2 * i * i)) {
return false;
}
}
}
return true;
}
}