Project Euler #46: Goldbach's other conjecture
Question
Answer : 5777
Hacker Rank Problem
Solution
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false.15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
Answer : 5777
Hacker Rank Problem
Solution
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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | import java.util.*; public class Solution { private static boolean[] prime = null; public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int numberOfTestCases = in.nextInt(); generatePrimes(); for(int i=0;i<numberOfTestCases;i++) { int res=0; int n = in.nextInt(); for(int j=2;j<=n;j++) { if(prime[j]) { int diff=n-j; if(diff%2==0 && isPerfectSquare(diff/2)) res+=1; } } System.out.println(res); } } public static boolean isPerfectSquare(int input) { int root = (int) Math.sqrt(input); return input == root * root; } public static void generatePrimes() { int limit = 1000000; prime = new boolean[limit+1]; prime[2] = true; prime[3] = true; int root = (int) Math.ceil(Math.sqrt(limit)); //Sieve of Atkin for prime number generation for (int x = 1; x < root; x++) { for (int y = 1; y < root; y++) { int n = 4 * x * x + y * y; if (n <= limit && (n % 12 == 1 || n % 12 == 5)) prime[n] = !prime[n]; n = 3 * x * x + y * y; if (n <= limit && n % 12 == 7) prime[n] = !prime[n]; n = 3 * x * x - y * y; if ((x > y) && (n <= limit) && (n % 12 == 11)) prime[n] = !prime[n]; } } for (int i = 5; i <= root; i++) { if (prime[i]) { for (int j = i * i; j < limit; j += i * i) { prime[j] = false; } } } } } |
Comments
Post a Comment