java - 从p和q为质数时找出n = p * q的'p'和'q'

我收到了这个问题。

n = 77

n = p*q

p and q is a prime number

用蛮力使p和q的发现者。

到目前为止，我的代码：

public class If {

    public static void main(String[] args) {

        int p = 3, q = 3;
        int n = 77;
        int temp = p*q;
        boolean flagp, flagq = false;
        while (temp != n && p <= 77)
        {
            for(int i = 2; i <= p/2; ++i)
            {
                // condition for nonprime number
                if(p % i == 0)
                {
                    flagp = true;
                    break;
                }
                p = p+2;
                q = 3;
                for(int j = 2; j <= q/2; ++j)
                {
                    // condition for nonprime number
                    if(q % j == 0)
                    {
                        flagq = true;
                        break;
                    }
                    q = q+2;
                    temp = p*q;
                }
            }
        }
        System.out.println(temp);
    }
}

我能够找到素数检查。但是我似乎找不到如何循环并找到匹配的p和q的方法。

最佳答案

我为您提供解决方案（使用BigInteger）：

import java.math.BigInteger;

public class If {

    //The first prime number
    public static final BigInteger INIT_NUMBER = new BigInteger("2");

    public static void main(String[] args) {

        //Initialise n and p
        BigInteger n = new BigInteger("77");
        BigInteger p = INIT_NUMBER;

        //For each prime p
        while(p.compareTo(n.divide(INIT_NUMBER)) <= 0){

            //If we find p
            if(n.mod(p).equals(BigInteger.ZERO)){
                //Calculate q
                BigInteger q = n.divide(p);
                //Displays the result
                System.out.println("(" + p + ", " + q + ")");
                //The end of the algorithm
                return;
            }
            //p = the next prime number
            p = p.nextProbablePrime();
        }
        System.out.println("No solution exists");
    }
}

注意：BigInteger类包含许多操作素数的函数。这样可以节省大量时间，并且避免了与大数相关的计算错误。