Finden eines 'p' und 'q' von n = p * q aus, wenn p und q Primzahlen sind

Question

Ich wurde diese Frage gegeben.

n = 77 

n = p*q 

p and q is a prime number 

Machen Sie den Finder von p und q mit roher Gewalt.

Mein Code so weit:

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

konnte ich die Überprüfung der Primzahl finden. Aber ich kann nicht finden, wie es zu loopen und finden Sie die passenden und q.

Answer 1

Ich habe eine Lösung für Sie (mit 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"); 
    } 
} 

Hinweis: Die BigInteger Klasse viele Funktionen enthält die Primzahlen zu manipulieren. Dies spart viel Zeit und vermeidet die mit großen Zahlen verbundenen Berechnungsfehler.

Answer 2

Sie brauchen keine Schleife für p und eine für q. Immer wenn Sie ein q so finden, dass n%q == 0, können Sie p = n/q berechnen. Dann machen Sie eine Funktion, um zu überprüfen, ob p und q beide Primzahlen sind, und wenn dies der Fall ist, stoppen Sie die Ausführung der Schleife und drucken Sie sie aus.

Brute Force bearbeiten: meine schlechte, rohe Gewalt ist nicht mein Ding, unsere Lehrer schließen uns in den Uni-Keller und schlagen uns mit Ketten, wenn wir es verwenden, um bestimmte Probleme zu lösen. Also, die Art und Weise Brute Force hier zu verwenden ist einfach die Multiplikation aller möglichen p und q von 2 bis n/2 und prüfen, ob p*q == n. Keine Optimierungen oder Einschränkungen mehr, um es zu einem schönen und langsamen Brute-Force-Algorithmus zu machen.

PD: Jetzt habe ich bemerkt, vielleicht ist das nicht wirklich rohe Gewalt und Algorithmen Klassen haben meine Gedanken gestört. Gott sei Dank bin ich nicht mit Eulers Theorem gegangen.

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: ein wenig sinnvollere Lösung

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

Der General Number Field Sieve (GNFS) Algorithmus ist der effizienteste Algorithmus Primfaktoren zu finden (bis jetzt), aber es ist schwieriger, zu programmieren als die oben genannten. Wenn Sie mit wirklich großen Zahlen umgehen, sollten Sie GNFS verwenden.