Java 中数字的最大质因数

Question

我在解决这个问题时试图找到一个数的最大质因数 here。我认为我做的一切都是对的，但是其中一个测试用例（#2）失败了，我想不出任何可能失败的角落案例。这是我的代码，请看看并尝试发现一些东西。

public class ProblemThree
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int i = 0; i < T; i++)
        {
            System.out.println(largestPrime(scanner.nextLong()));
        }
    }

    private static long largestPrime(long n)
    {
        while (n % 2 == 0)
        {
            n = n / 2;  // remove all the multiples of 2
        }
        while (n % 3 == 0)
        {
            n = n / 3; // remove all the multiples of 2
        }

        // remove multiples of prime numbers other than 2 and 3
        while (n >= 5)
        {
            boolean isDivisionComplete = true;
            for (long i = 5; i < Math.ceil(Math.sqrt(n)); i++)
            {
                if (n % i == 0)
                {
                    n = n / i;
                    isDivisionComplete = false;
                    break;
                }
            }
            if (isDivisionComplete)
            {
                break;
            }
        }
        return n;
    }
}

基本上，我正在做的是：

Largest_Prime(n):
1. Repeatedly divide the no by any small number, say x where 0 < x < sqrt(n).
2. Then set n = n/x and repeat steps 1 and 2 until there is no such x that divides n.
3  Return n.

Answer 1

提取质因数的一种简单方法如下：

/**
 * Prime factors of the number - not the most efficient but it works.
 *
 * @param n - The number to factorise.
 * @param unique - Want only unique factors.
 * @return - List of all prime factors of n.
 */
public static List<Long> primeFactors(long n, boolean unique) {
  Collection<Long> factors;
  if (unique) {
    factors = new HashSet<>();
  } else {
    factors = new ArrayList<>();
  }
  for (long i = 2; i <= n / i; i++) {
    while (n % i == 0) {
      factors.add(i);
      n /= i;
    }
  }
  if (n > 1) {
    factors.add(n);
  }
  return new ArrayList<>(factors);
}

第一个循环是个问题。他们会将所有偶数减少到 1 - 因此缺少 2 作为因素。更改代码以使用：

while (n > 2 && n % 2 == 0) {
  n = n / 2;  // remove all the multiples of 2
}
while (n > 3 && n % 3 == 0) {
  n = n / 3; // remove all the multiples of 2
}

您还有其他问题 - 例如您报告 25 的最大质因数为 25，49 的最大质因数为 49。

只需运行使用您和我的代码来查看您的代码在哪里失败：

for (long i = 1; i < 1000; i++) {
  long largestPrime = largestPrime(i);

  List<Long> primeFactors = primeFactors(i, true);
  if (primeFactors.size() > 0) {
    Collections.sort(primeFactors, Collections.reverseOrder());
    long highestFactor = primeFactors.get(0);
    if (largestPrime != highestFactor) {
      System.out.println("Wrong! " + i + " " + largestPrime + " != " + primeFactors);
    }
  } else {
    System.out.println("No factors for " + i);
  }
}

Answer 2

当您输入 16 largestPrime 函数 return 1. 和当输入是 3 的幂时是这样。

Answer 3

为什么要删除 2 的倍数和 3 的倍数？这样，如果您有一个数字是 2 和 3 的幂的任意组合，您将得到答案 1，这显然是错误的。

对于这个问题，您可以使用从 2 到 sqrt(n) 循环的天真方法，并存储除以 n 的最大数，当您完成循环时，只需 return 您找到的最高除数。

Answer 4

1 放弃 2 和 3 的循环。否则，您不会得到 2、2x2、3、2x3，... 2 和 3 的所有倍数

2 将循环更改为在 2（而不是 5）处停止：

while (n >= 2)
{

3 如果 2

停止

if (n==2) return 2;

4 循环从 2

和

5 循环直到 sqrt(n)，<= 而不仅仅是 <（如果不是，你不会得到素数 X 素数）

for (long i = 2; i <= Math.ceil(Math.sqrt(n)); i++)

Answer 5

详细算法说明：您可以通过保留三个变量来做到这一点：您要分解的数字 (A) 当前除数存储 (B) 最大的除数存储 (C) 最初，让 (A) 成为您感兴趣的数字 - 在本例中，它是 600851475143。然后让 (B) 成为 2。有一个条件检查 (A) 是否可以被 (B) 整除。如果它可以整除，则将 (A) 除以 (B)，将 (B) 重置为 2，然后返回检查 (A) 是否可以被 (B) 整除。否则，如果 (A) 不能被 (B) 整除，则将 (B) 递增 +1，然后检查 (A) 是否可以被 (B) 整除。运行直到 (A) 为 1 的循环。 (3) 你 return 将是 600851475143 的最大质因数。

 public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        long n = in.nextLong();
        long A=n;
        long B=2;
        long C=0;
        while(Math.pow(B,2)<=A)
            {
            if(A%B==0)
                {
                C=B;
                A=A/B;
                B=2;
            }
            else
               B++;

        }
           if(A>=C)
            C=A;
           if(A==1)
               { C=2;
                break;
               }
         System.out.println(C);   
    }
}

Java 中数字的最大质因数

Largest prime factor of a number in Java

java

algorithm

primes

prime-factoring