检查一个数是否是两个素数的和

Question

题目是检验一个随机数n可以是2个随机质数之和。例如，

if n=34 the possibilities can be (3+31), (5+29), (17+17)...

到目前为止，我已经设法将素数保存到数组中，但不知道如何检查 n 是否是 2 个素数的总和。

这是我的部分代码：

public static void primeNumbers(int n) {
    int i = 0, candidate = 2, countArray = 0, countPrime = 0;
    boolean flag = true;

    while (candidate <= n) {
        flag = true;
        for (i = 2; i < candidate; i++) {
            if ((candidate % i) == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            countPrime++;
        }
        candidate++;
    }
    int[] primeNumbers = new int[countPrime];


    while (candidate <= n) {
        flag = true;
        for (i = 2; i < candidate; i++) {
            if ((candidate % i) == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            primeNumbers[countArray] = candidate;
        }
        candidate++;
        countArray++;
    }

    for (i = 0; i <= primeNumbers.length; i++) {

    }
}

首先我计算了 1-n 之间有多少个素数，这样我就可以为素数声明和初始化我的数组。然后我将素数保存到数组中。但是现在我不知道如何检查 n 是否是 2 个素数的总和。

Answer 1

鉴于您已经有了 "prime numbers less than the given number" 的列表，检查两个素数是否可以和给定的数相加是一项非常简单的任务。

for(int i=0; i<array.length; i++){

    int firstNum = array[i];
    int secondNum = givenNum - firstNum;

    /* Now if it is possible to sum up two prime nums to result into given num, secondNum should also be prime and be inside array */

    if(ArrayUtils.contains(array, secondNum)){
        System.out.println("Yes, it is possible. Numbers are "+ firstNum + " and " + secondNum);
    }
}

编辑：ArrayUtils 是 Apache Commons Lang 库的一部分但是，您可以使用 ArrayList 而不是使用 contains 方法。

Answer 2

您不必检查从 1 到给定数字的所有质数，甚至不需要数组。

算法一即可；

First of all write a function that checks whether a given number is prime. Split the number into two parts, 0 and the remaining value(the number itself). Now start decreasing the number part by 1 and start adding 1 to 0 simultaneously. Stop when the number part which we are decreasing becomes 0 or both the parts are prime numbers.

另一种算法可以这样；（与接受的答案相似）

Start subtracting prime numbers from the given number starting from 2.Check whether the subtraction is also prime. The time you get the subtraction as a prime number, stop , you have got the two prime numbers that sum up to the given number.

检查一个数是否是两个素数的和

Check whether a number is a sum of two prime numbers

java

arrays

primes