Гипотеза Гольдбаха

Question

Согласно гипотезе Гольдбаха, любое четное число больше 2 может быть представлено в виде суммы двух простых чисел. Я написал программу проверки этой гипотезы для первых 500 чисел. Задача состоит в том, чтобы упростить код; нужен код без использования флагов.

public class App {

    public static void main(String[] args) {

    System.out.println((4) + " " + "2" + " " + "2");

        for(int i = 6; i <= 1000; i += 2) {
            for(int j = 3; j <= i; j+=2) {
                boolean isPrime = true;

                for(int k = 3; k <= Math.sqrt(j); k+=2) {
                    if(j % k == 0) {
                        isPrime = false;
                        break;
                    }
                }
                for(int k = 3; k <= Math.sqrt((i - j)); k+=2) {
                    if((i - j) % k == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if(isPrime) {
                    System.out.println((i) + " " + (j) + " " + (i - j));
                    break;
                }
                if(isPrime=false) {
                    System.out.println("Conjecture is wrong");
                    break;
                }
            }
        }
    }
}

Answer 1

Если не сильно заморачиваться со скоростью (так, умеренно заморочиться, но без решета Эратосфена), то я бы сначала накидал функцию, которая скажет, простое число или нет

private static boolean isPrime(int number) {
    for (int i = 2; i * i <= number; i++) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Потом нашел бы все простые числа в диапазоне 2-1000

HashSet<Integer> primes = new HashSet<>();
for(int i = 3; i < 1000; i ++){
    if(isPrime((i))) primes.add(i);
}

Ну и в итоге пошел бы чекать все возможные суммы (вы у себя один вариант суммы ищете, я все варианты показываю, сами догадаетесь, где break поставить если надо один вариант)

for(int i=2; i<1000; i+=2){
    for(int prime : primes){
        if (prime <= i/2 && primes.contains(i - prime))
            System.out.println((i) + " " + (prime) + " " + (i - prime));
    }
}

Вот и вся магия, код целиком

public class Main {

    public static void main(String[] args) {
        
        HashSet<Integer> primes = new HashSet<>();
        for (int i = 3; i < 1000; i++) {
            if (isPrime((i))) primes.add(i);
        }

        for (int i = 2; i < 1000; i+=2) {
            for (int prime : primes) {
                if (prime <= i/2 && primes.contains(i - prime))
                    System.out.println((i) + " " + (prime) + " " + (i - prime));
            }
        }
    }

    private static boolean isPrime(int number) {
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Answer 2

Слишком много вложенности в коде. Читаемость от такого падает в ноль. Производительность, кстати, тоже. Я бы в начале искал все простые числа, а уже потом запрашивал их из хешированной коллекции.

public class App {

    public static void main(String[] args) {
        
        int number = 100000;
        
        Set<Integer> allPrimes = allPrimes(number);        
        x:for (int i = 4; i <= number; i+=2) {            
            for (Integer prime : allPrimes) {
                if (allPrimes.contains(i-prime)) {
                    System.out.println(i + " = " + prime + " + " + (i-prime));
                    continue x;
                }
            }
            throw new RuntimeException("Incorrect result");
        }

    }

    private static Set<Integer> allPrimes(int numb) {
        return IntStream.range(2, numb + 1)
                .filter(i -> isPrime(i))
                .mapToObj(Integer::valueOf)
                .collect(Collectors.toSet());
    }

    private static boolean isPrime(int numb) {
        int limit = (int) Math.sqrt(numb);
        return IntStream.range(2, limit + 1).noneMatch(i -> numb % i == 0);
    }

}

БЛОГ НА HUSL

Гипотеза Гольдбаха

Ответы (2 шт):