解決項目歐拉問題＃41的提示

我想通過計算從99888888到80000000（這需要很長時間:(），我得到了98765431作爲答案的Java項目歐拉的Problem 41，但我得到的答案不正確。誰能告訴我沒有得到正確答案的原因，我怎樣才能加快我的程序？解決項目歐拉問題＃41的提示

來源

2010-01-17 Jazzy

'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位數字和上升，篩選所有素數，然後，採取最大的一個

來源

2010-01-17 13:16:49

這感覺就像要走的路。 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排列。

來源

2012-08-16 02:27:25 Cody

你必須更深入地解釋，恐怕 - 唯一可能的主要泛數數字是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毫秒。

來源

2014-05-24 17:46:12

爲了得到一個「合理的」時間的解決方案，你需要根據特殊的屬性，一些是被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毫秒。

來源

2015-01-11 19:31:55

解決項目歐拉問題＃41的提示

回答

相關問題