从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
。
我对你(使用的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类包含许多操控功能的素数。这可以节省大量时间并避免与大数字相关的计算错误。
这太棒了。但是你能给出评论来或多或少地解释代码的作用吗? –
当然可以...... –
@ChristianHardjono你明白了吗? –
你不需要一个循环的p和一个q。每当你发现一个这样的n%q == 0
,你可以计算p = n/q
。然后,创建一个函数来检查p和q是否都是素数,如果是,则停止循环执行并打印它们。
蛮力编辑:我的坏,蛮横不是我的东西,我们的老师把我们关在uni地下室,并用链子打我们,如果我们用它来解决某些问题。所以,在这里使用暴力的方法是将所有可能的p和q乘以2到n/2,并检查p*q == n
。没有更多的优化或限制,使它成为一个美丽而缓慢的蛮力算法。
PD:现在我已经注意到了,也许这实际上并不是蛮力,算法类已经打乱了我的想法。感谢上帝,我还没有用欧拉定理。
这是开始聪明,而不是*蛮力*可能需要... –
是的,但也许他被要求用蛮力的目的。 –
这正是我的意思,你的建议可能是*聪明*被认为*蛮力*! –
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));
不适用于n> 2147483647 –
的一般数域筛(GNFS)算法是最有效的算法找出主要因素(到现在),但它更困难编程比上面提到的要多。如果你处理的是非常大的数字,你应该使用GNFS。
您可以先找到所有素数并将它们保存在列表中。然后你可以使用两个嵌套for循环来检查哪个组合工作。 – Christian
不要在for循环中声明i和j是本地的。当你突破时你需要这些价值。其他一半的变量是多余的。这包括p,q,temp,flagp,flagq。 – Necreaux
我可以考虑列出小于'n'的所有素数。遍历列表并假设它是'p'。计算分部'n/p' =>'q'。检查'q'是否为素数。 –