如何計算強大的數字

Question

今天我遇到了一個相當特殊的Java編碼問題，我希望得到一些解釋。

這裏是提出的問題：

甲冪數是正整數米，對於每一個素數p 分M，P * P也劃分米。

 (a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, 
     which are 1 and the prime number itself, the first prime numbers are: 2, 3, 5, 7, 11, 13, ...) 

     The first powerful numbers are: 1, 4, 8, 9, 16, 25, 27, 32, 36, ... 

     Please implement this method to 
     return the count of powerful numbers in the range [from..to] inclusively. 

我的問題是，究竟是一個強大的數字？這裏是我的定義：

1. 一個正整數 和
2. 一個正整數，是一個素數 和
3. 一個正整數，是由primeValX * primeValX分割，也整除可分primeValX

我的說法錯了嗎？因爲當我將斷言應用於我的代碼時，它不會返回正確的結果。

假想的結果應該是1，4，8，9，16

下面是實際的結果我得到：

i: 4 j: 2 ppdivm: 0 pdivm: 0 
powerful num is: 4 
i: 8 j: 2 ppdivm: 0 pdivm: 0 
powerful num is: 8 
i: 9 j: 3 ppdivm: 0 pdivm: 0 
powerful num is: 9 
i: 12 j: 2 ppdivm: 0 pdivm: 0 
powerful num is: 12 
i: 16 j: 2 ppdivm: 0 pdivm: 0 
powerful num is: 16 
total count: 5 

這裏是我的代碼：

public static int countPowerfulNumbers(int from, int to) { 
      /* 
       A powerful number is a positive integer m that for every prime number p dividing m, p*p also divides m. 

       (a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, 
       which are 1 and the prime number itself, the first prime numbers are: 2, 3, 5, 7, 11, 13, ...) 

       The first powerful numbers are: 1, 4, 8, 9, 16, 25, 27, 32, 36, ... 

       Please implement this method to 
       return the count of powerful numbers in the range [from..to] inclusively. 
      */ 
      int curCount=0; 
      int curPrime; 
      int[] rangePrime; 
      int pdivm, ppdivm; 
      for(int i=from; i<=to; i++){ 
       if(i<0){ 
        continue; 
       } 


       rangePrime = primeRange(1 , i); 
       for(int j=0; j<rangePrime.length-1; j++){ 

        pdivm = i%rangePrime[j]; 
        ppdivm = i%(rangePrime[j]*rangePrime[j]); 
        //System.out.println("ppdivm: " + ppdivm + " pdivm: " + pdivm); 

        if(pdivm == 0 && ppdivm == 0){ 
         curCount++; 
         System.out.println("i: " +i + " j: " + rangePrime[j] + " ppdivm: " + ppdivm + " pdivm: " + pdivm); 

         System.out.println("powerful num is: " + i); 
        } 

       } 


      } 

      System.out.println("total count: " + curCount); 
      return curCount; 
     } 

     public static int[] primeRange(int from, int to){ 

      List<Integer> resultant = new LinkedList<Integer>(); 
      for(int i=from; i<=to; i++){ 
       if(isPrime(i)== true){ 
        resultant.add(i); 
       } 
      } 

      int[] finalResult = new int[resultant.size()]; 
      for(int i=0; i<resultant.size(); i++){ 
       finalResult[i] = resultant.get(i); 

      } 

      return finalResult; 
     } 

     public static boolean isPrime(int item){ 

      if(item == 0){ 
       return false; 
      } 

      if(item == 1){ 
       return false; 
      } 

      Double curInt, curDivisor, curDivi, curFloor; 
      for(int i=2; i<item; i++){ 
       curInt = new Double(item); 
       //System.out.println(curInt); 
       curDivisor = new Double(i); 
       //System.out.println(curDivisor); 

       curDivi = curInt/curDivisor; 
       //System.out.println(curDivi); 

       curFloor = Math.floor(curDivi); 

       if(curDivi.compareTo(curFloor) == 0){ 
        return false; 
       } 
      } 

      return true; 
     } 

    public static void main(String[] args){ 

     System.out.println(isPrime(1)); 

     int[] printout = primeRange(1, 10); 
     for(int i=0; i<printout.length; i++){ 
      System.out.print(" " + printout[i] + " "); 
     } 
     System.out.println(""); 
     countPowerfulNumbers(1, 16); 

     return; 
    } 

謝謝！

Answer 1

根據Wiki article on Powerful Numbers定義錯誤。

它說，對於每個素數p除以你的數字，p^2也劃分該數字。

因爲你沒有對所有素數進行限制，所以你得到了12。所以12可以被2和2^2 = 4整除。但是，它也可以被3整除，但不是3^2 = 9。

Answer 2

您的定義與引用的定義不符。第1部分是正確的。第2部分和（如Draco18評論）3不正確。

你的第二點是差不多第一個副本。唯一的區別是1是一個正整數，但它不能被任何素數整除（1本身是not prime，因爲您的isPrime()函數正確返回）。

你的第三點始於（在我看來）條件的尷尬措辭。它似乎建議檢查是否(i % (p*p)) == 0第一，然後檢查(i % p) == 0，那麼這將是多餘的，允許失蹤，其中(i % (p*p)) != 0但(i % p) == 0，因爲第一次檢查將導致第二個被跳過的重要情況。幸運的是，您的代碼在正確的（p，然後p*p）順序中執行檢查。

現在我們來看看第三點中的主要錯誤，Draco18和Frank試圖指出的一點。您聲明一個強大的數字必須可以被a primeValX * primeValX和a primeValX整除。給定的定義說明一個強大的數字必須可以被primeValX * primeValX整除每 primeValX它可以被整除。

有什麼區別？您的版本需要有可以分割強大數字的primeValX * primeValX at least one。因此它將排除1，因爲它不能被任何素數整除，並且包括12之類的數字，它可以被素數2和2*2整除。

給定的版本要求所有素數分割一個強大的數字，素數的平方也將它們分開。這有兩個含義：

1. 如果沒有候選人，所有或全部成功默認。因此，由於沒有因爲1測試失敗的素數因子，所以1是一個強大的數字。
2. 只要找到一個可以工作的p和p*p，就不能走捷徑併成功。你必須測試所有素數因子及其正方形之前你可以知道它是否是是是一個強大的數字。你可以失敗，只要你得到一個素數除數的平方是而不是也是一個除數。

Answer 3

澄清，諸位碼校正，且快速的方法下面

你定義有錯誤：

2：一個正整數，是由一個素數整除=>它是任何定義非質數

3：一個正整數，是由一個primeValX primeValX整除並且還整除一個primeValX =>相當於一個正整數，是由一個primeValX primeValX整除的（並且其包括asserti 2）

那麼你的定義是

「與一些素因子^ 2的任何不素數」我把原來的定義，你就把：

一個強大的數字爲正整數m表示每個質數 p除m，p * p也除m。

像這樣的：http://mathworld.wolfram.com/PowerfulNumber.html

然後我的算法：檢查你的電話號碼的每一個主要dividor X，如果X * X也爲dividor。如果不是，則結束。

我糾正你這樣的代碼

for(int i=from; i<=to; i++) 
     { 
     // CHANGE THERE (or <=3) 
     if(i<=1) 
      continue; 

我把一個標誌：

// by default: 
boolean powerfull=true; 

如果我是黃金本身，而不是強大的！

// if prime: finished ! 
if (isPrime(i)) 
    continue; 

最大的變化是在您的測試：

// RULE is: i divisor => ixi must be a dividor 
if(pdivm == 0) 
     if (ppdivm != 0) 
      { 
      // You lose ! 
      System.out.println("i: " +i + " j: " + rangePrime[j] + " ppdivm: " + ppdivm + " pdivm: " + pdivm); 
      powerfull=false; 
      } 

然後，在你的主循環：

if (powerfull) 
    { 
    curCount++; 
    System.out.println("powerful num is: " + i); 
    } 

第二種方法更快，特別是如果你的範圍大：

正如我的鏈接中指出的那樣：

對於a，b> = 1，強大的數字總是a^2b^3的形式。

然後：從2使一個循環範圍^ 1/2 另一個嵌入環2至範圍^三分之一 和繁殖

那樣：

int from=4; 
int to=100000; 

Set<Integer> set=new TreeSet<Integer>(); // automatically sorted 

// Max candidates 
int maxSquarecandidate= (int) Math.sqrt(to); 
int maxCubeCandidates=(int) Math.pow(to,1.0/3)+1; 

for (int candidate1=1; candidate1<maxSquarecandidate;candidate1++) 
    for (int candidate2=1; candidate2<maxCubeCandidates;candidate2++) 
     { 
     int result=candidate1*candidate1*candidate2*candidate2*candidate2; 

     if ((result!=1) && (result>=from) && (result<=to)) set.add(result); 
     } 

System.out.println(set); 

希望它幫助！