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

は、私が（のBigIntegerを使用して）あなたのためのソリューションを持っているのBigIntegerクラスは素数を操作するための多くの機能が含まれています。これにより、多くの時間を節約し、多数の計算エラーを回避します。

Answer 2

pのループとqのループは必要ありません。 n%q == 0などのqが見つかるたびに、p = n/qを計算することができます。次に、pとqがともに素数であるかどうかをチェックし、そうであればループ実行を停止して印刷します。

ブルートフォース編集：私の悪い、ブルートフォースは私のものではなく、私たちの教師は私たちを地下に閉じ込めて、特定の問題を解決するためにそれを使うとチェーンでぶつかります。したがって、ここでブルートフォースを使用する方法は、2からn/2までのすべての可能なpとqを単純に乗算して、p*q == nかどうかを確認することです。美しく、遅いブルートフォースアルゴリズムにするための最適化や制限はありません。

PD：今私は気づいたことがあります。これは実際にはブルートフォースではなく、アルゴリズムクラスが私の心を邪魔しました。私はオイラーの定理に行っていない神に感謝します。

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

注：

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

EDIT：もう少し便利なソリューション

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を使うべきです。