java - 如何计算强大的数字

Question

我今天遇到了一个相当奇怪的 Java 编码问题，我希望得到一些澄清。

这里是提出的问题:

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.

我的问题是一个强大的数字到底是什么？这是我的定义:

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 整除。