從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'

回答

相關問題