欧拉计划 #49 Java

Question

问题是 -

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

我写了这段代码 -

package Problems;

import java.util.ArrayList;
import java.util.LinkedList;

public class Pro49 {

    private static boolean isPrime(int n){
        if(n%2 == 0) return false;

        for(int i = 3; i<= Math.sqrt(n); i++){
            if(n%i == 0) return false;
        }

        return true;
    }

    private static boolean isPerm(int m, int n){
        ArrayList<Integer> mArr = new ArrayList<>();
        ArrayList<Integer> nArr = new ArrayList<>();

        for(int i = 0; i<4; i++){
            mArr.add(m%10);
            m /= 10;
        }

        for(int i = 0; i<4; i++){
            nArr.add(n%10);
            n /= 10;
        }

        return mArr.containsAll(nArr);
    }

    public static void main(String[] args) {

        LinkedList<Integer> primes = new LinkedList<>();

        for(int i = 1001; i<10000; i++){
            if(isPrime(i)) primes.add(i);
        }


        int k = 0;
        boolean breaker = false;
        for(int i = 0; i<primes.size() - 2; i++){
            for(int j = i + 1; j<primes.size() - 1; j++){
                if(isPerm(primes.get(i), primes.get(j))) {
                    k = primes.get(j) + (primes.get(j) - primes.get(i));

                    if(k<10000 && primes.contains(k) && isPerm(primes.get(i), k)) {
                        System.out.println(primes.get(i) + "\n" + primes.get(j) + "\n" + k);
                        breaker = true;
                        break;
                    }

                }
                if(breaker) break;
            }
            if(breaker) break;
        }


    }

}

我添加了打印行 System.out.println(primes.get(i) + "\n" + primes.get(j) + "\n" + k); 来检查数字。我得到的 1049、1499、1949 是错误的。（我猜至少1049是错误的）。

谁能指出我的code/logic哪里错了？任何帮助表示赞赏。

Answer 1

我认为您的逻辑出错的地方是您的 isPerm 方法。您正在使用 AbstractCollection#containsAll，据我所知， 仅检查参数是否至少出现在集合中一次。

即基本上可以

for(E e : collection)
    if(!this.contains(e)) return false;
return true;

因此，例如，4999 将是 49 的排列，因为 49 包含 4 和 9（而它显然不是基于您的示例）。

您的方法似乎适用于这些值的原因是您循环的时间固定 - 即 4。对于像 49 这样的数字，您最终会得到 {9, 4, 0, 0} 而不是 {9, 4}。做这样的事情：

while(n != 0) {
    nArr.add(n%10);
    n /= 10;
}

你会得到正确的数字 Lists（并且看到 containsAll 不起作用。）

在别处添加 4 位数限制（例如在您的循环中。）

也许你可以检查每个数字出现的次数。例如：

int[] occurrencesA = new int[10], occurrencesB = new int[10];
for(; m != 0; m /= 10)
    occurrencesA[m % 10]++;
for(; n != 0; n /= 10)
    occurrencesB[n % 10]++;
for(int i = 0; i < 10; i++)
    if(occurrencesA[i] != occurrencesB[i]) return false;
return true;

Answer 2

我找到了 isPerm

的可能替代方案

private static boolean isPerm(int m, int n){
        ArrayList<Integer> mArr = new ArrayList<>();
        ArrayList<Integer> nArr = new ArrayList<>();

        final String mS = Integer.toString(m);
        final String nS = Integer.toString(n);

        if(mS.length() != nS.length()) return false;

        for(int i = 0; i<mS.length(); i++){
            mArr.add(m%10);
            m /= 10;
        }

        for(int i = 0; i<nS.length(); i++){
            nArr.add(n%10);
            n /= 10;
        }

        return (mArr.containsAll(nArr) && nArr.containsAll(mArr));
    }

这是我的正确答案。另一种选择是由下面的其他人发布的。

欧拉计划 #49 Java

Project Euler #49 Java

java

primes

permutation