从p和q是质数时找出n = p * q的'p'和'q'

我被给了这个问题。从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。

来源

2017-07-18 Christian Hardjono

您可以先找到所有素数并将它们保存在列表中。然后你可以使用两个嵌套for循环来检查哪个组合工作。 – Christian

不要在for循环中声明i和j是本地的。当你突破时你需要这些价值。其他一半的变量是多余的。这包括p，q，temp，flagp，flagq。 – Necreaux

我可以考虑列出小于'n'的所有素数。遍历列表并假设它是'p'。计算分部'n/p' =>'q'。检查'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类包含许多操控功能的素数。这可以节省大量时间并避免与大数字相关的计算错误。

来源

2017-07-18 11:09:15

这太棒了。但是你能给出评论来或多或少地解释代码的作用吗？ –

当然可以...... –

@ChristianHardjono你明白了吗？ –

你不需要一个循环的p和一个q。每当你发现一个这样的n%q == 0，你可以计算p = n/q。然后，创建一个函数来检查p和q是否都是素数，如果是，则停止循环执行并打印它们。

蛮力编辑：我的坏，蛮横不是我的东西，我们的老师把我们关在uni地下室，并用链子打我们，如果我们用它来解决某些问题。所以，在这里使用暴力的方法是将所有可能的p和q乘以2到n/2，并检查p*q == n。没有更多的优化或限制，使它成为一个美丽而缓慢的蛮力算法。

PD：现在我已经注意到了，也许这实际上并不是蛮力，算法类已经打乱了我的想法。感谢上帝，我还没有用欧拉定理。

来源

2017-07-18 11:03:03

这是开始聪明，而不是*蛮力*可能需要... –

是的，但也许他被要求用蛮力的目的。 –

这正是我的意思，你的建议可能是*聪明*被认为*蛮力*！ –

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));

来源

2017-07-18 11:20:58 PrincePolka

不适用于n> 2147483647 –

的一般数域筛（GNFS）算法是最有效的算法找出主要因素（到现在），但它更困难编程比上面提到的要多。如果你处理的是非常大的数字，你应该使用GNFS。

来源

2017-07-24 12:47:49

从p和q是质数时找出n = p * q的'p'和'q'

回答

相关问题