Блог

Вот вопрос: «Подготовьте Java-программу, которая будет принимать неотрицательное четное число (больше 2) и извлекать два простых числа при добавлении, сумма эквивалентна вводимому пользователем неотрицательному четному числу.

Пример вывода.

 "Enter Number: 20" 
"17 amp; 3" or "3 amp; 17"
  

Я попытался закодировать простое число между двумя введенными числами. но я не знаю, как закодировать вопрос выше. 🙁

 import java.util.Scanner;


public class PrimeNumberInInterval{ 
  
    public static void main(String[] args) 
    { 
        Scanner input = new Scanner(System.in); 
        int n1, n2, i, j, pn; 
        System.out.println("Starting number: "); 
        n1 = input.nextInt();
        System.out.println("Ending number: "); 
        n2 = input.nextInt();
  
        System.out.println("The prime numbers in between are: " n1   n2); 
     
        for (i = n1; i <= n2; i  ) { 
            if (i == 1 || i == 0) 
                continue; 
            pn = 1; 
            for (j = 2; j <= i / 2;   j) { 
                if (i % j == 0) { 
                    pn = 0; 
                    break; 
                } 
            } 
            if (pn == 1) 
                System.out.println(i); 
        } 
    } 
}
  

В математических терминах эта проблема называется гипотезой Гольдбаха, где каждое четное целое число, большее 2, может быть выражено как сумма двух простых чисел. Теперь один подход к решению этой проблемы включает в себя выполнение 2 вещей:

1. Сгенерируйте все простые числа, меньшие, чем 2 * n 2 где n заданное число. Эту генерацию простых чисел можно легко выполнить с помощью алгоритма сита Сундарама
2. После того, как вы сгенерировали простые числа, начните вычитание каждого простого числа из заданного числа n и проверьте, является ли разница также простым числом или нет. Если да, то вы нашли свой результат.

Простая реализация алгоритма сита Сундарама может быть выполнена с использованием boolean массива и целых List чисел:

 List<Integer> primeNumbers = new ArrayList<>();
    public void generatePrimes(int n) {
        // As we want prime numbers smaller than n,
        // reduce n to half (calling this as nHalf)
        int nHalf = (n - 1) / 2;

        // This marker is used to mark the numbers which are of the form i   j   2*i*j
        // from the rest where 1 <= i <= j as per Sieve of Sundaram algorithm
        boolean[] marker = new boolean[nHalf   1];

        // Mark all numbers of the form i   j   2*i*j
        for(int i = 1; i <= nHalf; i  ) {
            for(int j = i; (i   j   2 * i * j) <= nHalf; j  ) {
                marker[i   j   2 * i * j] = false;
            }
        }
        // Add 2 as it is a prime number
        primeNumbers.add(2);

    // Once all the numbers of the form i   j   2*i*j are marked, remaining numbers should be
    // doubled and incremented by 1 to get odd prime numbers
        for(int i = 1; i <= nHalf; i  ) {
            if(marker[i] == false) {
                primeNumbers.add(2 * i   1);
            }
        }
    }
  

Теперь получить простые числа для данного числа num так же просто, как:

 generatePrimes(num);
        for(int i = 0; primeNumbers.get(i) <= num/2; i  ) {
            // find difference by subtracting current prime number from given number num
            int difference = num - primeNumbers.get(i);

            // Check if difference is also a prime number.
            if(primeNumbers.contains(difference)) {
                System.out.println(primeNumbers.get(i)   " AND "   difference);
                break;
            }
        }