Project Euler > Problem 46 > Goldbach's other conjecture (Java Solution)

Problem:

It was proposed by Christian Goldbach that every odd composite number can 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.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

Solution:

5777

Code:
The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/* 
 * Solution to Project Euler problem 46
 * By Nayuki Minase
 * 
 * http://nayuki.eigenstate.org/page/project-euler-solutions
 * https://github.com/nayuki/Project-Euler-solutions
 */


public final class p046 implements EulerSolution {
 
 public static void main(String[] args) {
  System.out.println(new p046().run());
 }
 
 
 public String run() {
  for (int i = 2; ; i++) {
   if (!satisfiesConjecture(i))
    return Integer.toString(i);
  }
 }
 
 
 private boolean satisfiesConjecture(int n) {
  if (n % 2 == 0 || isPrime(n))
   return true;
  
  // Now n is an odd composite number
  for (int i = 1; i * i * 2 <= n; i++) {
   if (isPrime(n - i * i * 2))
    return true;
  }
  return false;
 }
 
 
 private boolean[] isPrime = {};
 
 private boolean isPrime(int n) {
  if (n >= isPrime.length)
   isPrime = Library.listPrimality(n * 2);
  return isPrime[n];
 }
 
}

Read More

Counting the Number of Primes Entered in Java

Problem:

Write a program that reads positive integers from the keyboard until the user enters 0. Then the program prints the number of prime numbers entered.

Output:

Enter prime numbers seperated by space(0 to quit):
2 3 5 03

Solution:

import java.util.Scanner;

public class lauprob5

{
 public static void main(String[] args) 
 
 {
  Scanner scan = new Scanner (System.in);
  
     //We need something to use to get into the loop
     int prime = 1, count = 0;
     
     System.out.println("Enter prime numbers seperated by space(0 to quit):");
     
     //We'll keep on looping and scanning till we scan a 0
     while (prime != 0)
      
     {
      
     prime = scan.nextInt();
     
     //It's easier to prove that a number that we think is prime
     // isn't really prime because a prime is a number that's
     //only divisible by one and itself
     //so we'll make our initial boolean: 
     boolean isPrime = true; 
     
     //there are no prime numbers less than 2 so we need this
     //to quickly prove that a number isn't prime, so how easy
     //to prove that a number isn't prime?
     if (prime < 2) isPrime = false; 
     
     for (long i = 2; i*i <= prime; i++)
      
     { 
      //if the prime is divisble by i, which a number
      //that is neither 1 or the entered number, then 
      //the number is NOT prime and the case is closed (break)
       if (prime % i == 0) 
       
       isPrime = false; 
      break; 
     } 
     
     //If after existing that loop, we never found 
     //any divisors of the number (and it's not less than true
     //then it is of course a prime number so we should
     //increase our variable that counts the number of scanned
     //prime numbers by one
     if (isPrime) 
      
      count ++;
     }
     System.out.print(count);
     } 
 }

Read More