当 p 和 q 是素数时，找到 n=p*q 的 'p' 和 'q' [英] Finding a 'p' and 'q' of n=p*q from when p and q are prime numbers

问题描述

我被问到这个问题.

n = 77

n = p*q

p and q is a prime number

用蛮力做 p 和 q 的查找器.

Make the finder of p and q with brute force.

到目前为止我的代码:

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.

I was able to find the prime number checking. But I can't seem to find how loop it and find the matching p and q.

推荐答案

我有一个解决方案(使用 BigInteger):

I have a solution for you (using 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 类包含许多操作素数的函数.这样可以节省大量时间并避免与大数相关的计算错误.

Note : The BigInteger class contains many functions to manipulate the prime numbers. This saves a lot of time and avoids the calculation errors associated with large numbers.

这篇关于当 p 和 q 是素数时，找到 n=p*q 的 'p' 和 'q'的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！