当 p 和 q 是质数时，找到 n=p*q 的 'p' 和 'q'

Question

有人问我这个问题。

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.

Answer 1

您不需要 p 循环和 q 循环。每当你找到一个 q 使得 n%q == 0，你就可以计算 p = n/q。然后，编写一个函数来检查p和q是否都是质数，如果是，则停止循环执行并打印它们。

蛮力编辑：我不好，蛮力不是我的事，我们的老师把我们关在大学地下室，如果我们用它来解决某些问题，就会用铁链打我们。所以，这里使用暴力的方法就是将所有可能的 p 和 q 从 2 乘以 n/2，然后检查是否 p*q == n。没有更多的优化或限制，使它成为一个美丽而缓慢的暴力算法。

PD：现在我注意到，也许这实际上并不是蛮力，算法类扰乱了我的思想。谢天谢地，我没有违背欧拉定理。

Answer 2

我有一个解决方案（使用 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 class 包含许多操作素数的函数。这样可以节省大量时间并避免与大数相关的计算错误。

Answer 3

import java.math.*;
import java.io.*;
class If {
  public static void main(String[] args) {
    int n=77, p=2, q=0;
    while (n%p>0) { p++; }
    q=77/p;
    System.out.println(new BigInteger(""+q).isProbablePrime(1)?p+" "+q:"No solution exists");
  }
}

编辑：一个更有用的解决方案

String out="";
String primeFactor(int n) {
  int p=2;
  while (n%p>0 && p<=n){p++;}
  out+=p;
  if (p<n){
    out+=" ";
    primeFactor(n/p);
  }
  return out;
}
System.out.println(primeFactor(77));

Answer 4

通用数域筛 (GNFS) 算法是寻找素因子的最有效算法（到目前为止），但它比上面引用的算法更难编程。如果你处理非常大的数字，你应该使用 GNFS。

当 p 和 q 是质数时，找到 n=p*q 的 'p' 和 'q'

Finding a 'p' and 'q' of n=p*q from when p and q are prime numbers

java

rsa

brute-force