解决项目欧拉问题#41的提示

Question

我正在尝试解决Java中项目Euler的问题41,通过计算从99888888到80000000的数字(花了很长时间:(),我得到98765431作为答案,但我得到的答案不正确.有谁请告诉我没有得到正确答案的原因,我怎样才能加快我的计划？

Answer 1

pandigital数字不需要包含所有数字1 to 9,但全部来自1 to length.

因此,您需要尝试从1 to 91位开始上升所有排列,过滤所有素数,然后取最大值.

Answer 2

唯一可能的素数泛数字是那些长度为1、4 和 7 的数字，因为所有其他泛数字的数字之和都可以被 3 整除。

因此，您只需要测试7! = 5040排列即可。

Answer 3

为了在“合理的”时间内获得解决方案，您需要基于以下特殊性质的观察结果：如果数字的总和可被3整除，则该数字可被3整除：

                            divisible by 
 1+2+3+4 = 10               -  
 1+2+3+4+5 = 15             3 
 1+2+3+4+5+6 = 21           3
 1+2+3+4+5+6+7 = 28         - 
 1+2+3+4+5+6+7+8 = 36       3 
 1+2+3+4+5+6+7+8+9 = 45     3 

因此，“大”素数位数字具有4或7位数字。（大于3的素数不能被3整除）

因为要获得最大的数字，所以最好从7位数字开始，然后仅在找不到数字的情况下继续检查4位数字。当然，由于指定了4位数字，因此存在：2143。

现在，可能的解决方案如下所示：

public class P41 {

    public static void main(String[] args) {

        boolean wasFound = false;

        for (int nr = 7654321; nr >= 1234567; nr -= 2) { // even != prime
            if (isPandigital(nr) && isOddPrime(nr)) {
                System.out.println(nr);
                wasFound = true;
                break;
            }
        }

        if (!wasFound) {
            /* not <=, because 1234 is even */
            for (int nr = 4321; nr > 1234; nr -= 2) {
                if (isPandigital(nr) && isOddPrime(nr)) {
                    System.out.println(nr);
                    break;
                }
            }
        }
    }

    private static boolean isOddPrime(int x) {
        int sqrt = (int) Math.sqrt(x);
        for (int i = 3; i <= sqrt; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static int getNumberOfDigits(int x) {
        int count = 0;
        while (x > 0) {
            count++;
            x /= 10;
        }
        return count;
    }

    private static boolean isPandigital(int x) {
        int numberOfDigits = getNumberOfDigits(x);
        Set<Integer> digits = new HashSet<Integer>();
        for (int i = 1; i <= numberOfDigits; i++) {
            digits.add(i);
        }
        for (int i = 1; i <= numberOfDigits; i++) {
            digits.remove(x % 10);
            x /= 10;
        }
        if (digits.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

}

时间：8毫秒。