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

问题描述：

我想通过计算从99888888到80000000（这需要很长时间:(），我得到了98765431作为答案的Java项目欧拉的Problem 41，但我得到的答案不正确。谁能告诉我没有得到正确答案的原因，我怎样才能加快我的程序？解决项目欧拉问题＃41的提示

'98765431'不是pandigital素数，因为它不包含'2' – 2010-01-17 13:08:20

看问题的描述，他们从来不提的是，答案应该是基地10。这似乎有点草率，因为如果你选择适当的基地，我猜想存在任意大的pandigital素数。 – Benno 2010-01-17 13:21:55

答

一个pandigital号码不需要包含所有数字1 to 9，但所有从1 to length。

所以，你需要尝试所有的排列从1 to 9开始1位数字和上升，筛选所有素数，然后，采取最大的一个

这感觉就像要走的路。 9个元素只有362880个排列，因此这在合理的时间内计算是可行的。 – Buhb 2010-01-17 13:35:55

不是真的：362880 + 40320 + 5040 + 720 + 120 + 24 + 6 + 2 = 409112排列（记得添加8,7,6等数字的排列），其中包含538个素数 – 2010-01-17 13:58:09

+17

事实：如果总和一个整数的基数10位数是0 mod 3，该整数可以被3整除。因此，每9位数和8位数的pandigital数可以被3整除，并且不能是素数。 – 2010-01-17 15:07:48

答

唯一可能的素数pandigital是那些长度为 1，4，7 &因为每隔数pandigital具有其位被3整除

所以，总而言之，你只需要测试为7! = 5040排列。

你必须更深入地解释，恐怕 - 唯一可能的主要泛数数字是1,4和7，你是什么意思？首先，4不是素数。 – andrewsi 2012-10-01 02:55:52

答

这是问题的声明：

我们应该说是一个正数字是pandigital如果它利用了所有的数字1到n一次。例如，2143是一个4位数的pandigital，也是主要的。什么是最大的n位数字pandigital素数？

我写了一个程序，开始于987654321并倒计时。我检查了这个数字是否是pandigital，如果是，检查它是否为素数。

在我的Windows 8.1电脑上花了66秒才找到最大的素数pandigital。

当我测试了另一种方式，第一个素数，然后pandigital，程序超过66秒的方式。我取消了它。

当我申请GregS”尖约贴现所有9位和第8位pandigital号码，并开始从7654321倒计时，我的蛮力算法用了13毫秒。

答

为了得到一个“合理的”时间的解决方案，你需要根据特殊的属性，一些是被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位数字未找到。当然，存在一个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毫秒。

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

相关推荐