一类程序的质因数分解

Question

import java.util.Scanner;
public class JavaApplication1 {
  public static void main(String[] args) {
    Scanner kboard = new Scanner(System.in);
    int n = 0;
    int i = 1;
    System.out.println("Enter a positive number");
    n = kboard.nextInt();
    System.out.print("The Prime Factors of " + n + " are : ");
    value = 2;
    while (n > 1) {
        i = 1;
        if (n % i != 0){
           i = 1;
           i=i+1;
           if(n % i == 0){
               System.out.println(" "+ i);
           }
        }
        else {
            System.out.print("1 and " + n);
            break;
        }
    }
  }
}

这是我的程序，我大约一个月前开始编码，但程序只给出1和数字作为输出，而不是素数因子。

Answer 1

程序总是给出1作为输出，因为:

i = 1;
if (n % i != 0) {
    // ...
} else {
    System.out.print("1 and " + n);
    break;
}

由于i = 1, n % i != 0为假，因为任何n模块1都为0。所以else块总是被执行，你立即跳出while循环。

即使你解决了这个问题，这个程序中还有许多其他问题:

• 条件n > 1是无意义的，因为n在这个循环中永远不会改变，所以条件总是true。
• 检查% 1是没有意义的，因为每个数字都除以1。你应该从2.
开始检查

稍加改进，可以改进循环以查找因子:

List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
        factors.add(i);
    }
}

但这还远远不够好。它会找到所有因子，而不仅仅是质因数。例如，对于编号40，它将找到2, 4, 5, 8, 10，其中只有2和5是质数。一个简单的解决方案是添加另一个称为isPrime的方法来检查一个数字是否是素数。

Answer 2

这将为您完成简单的技巧:只需根据用户输入设置num。

List<Integer> result = new ArrayList<>();
            // Take out the 2s.
            while (num % 2 == 0)
            {
                result.Add(2);
                num /= 2;
            }
            // Take out other primes.
            int factor = 3;
            while (factor * factor <= num)
            {
                if (num % factor == 0)
                {
                    // This is a factor.
                    result.Add(factor);
                    num /= factor;
                }
                else
                {
                    // Go to the next odd number.
                    factor += 2;
                }
            }
            // If num is not 1, then whatever is left is prime.
            if (num > 1) result.Add(num);
            return result;

Answer 3

如果您想获得所有质因数，您可以尝试:

    int i = 2;
    while (n > 1) {
        if (n % i == 0) {
            System.out.print(" " + i);
            while ( n % i == 0 ) {
                n /= i;
            }
        }
        i++;
    }

如果是n = 960，则输出2 3 5。

如果n = 11，则打印11。

你怎么确定你没有考虑一个非素数?

• 第二个while循环尽可能地除数。所以，这个数字不会被4除以，因为它可以，它已经被2除以两次了。

---

如果您还想获得这些素数因子的指数，您可以使用0初始化变量，每次除法增加它，然后将其打印到标准输出:

    int i = 2;
    while (n > 1) {
        if (n % i == 0) {
            System.out.print(" " + i);
            int p = 0;
            while ( n % i == 0 ) {
                n /= i;
                p++;
            }
            System.out.print("^"+p);
        }
        i++;
    }

如果是n = 98，则输出2^1 7^2