testen ob Primzahl dauert bei größeren zahlen extrem lange

Status
Nicht offen für weitere Antworten.
A

anfänger15

Bekanntes Mitglied
Hallo
bei meinem Programm dauert es extrem lange um zu testen ob eine zahl eine Primzahl ist.Bei kleineren Zahlen geht es ja noch aber bei größeren dauert es meiner meinung nach viel zu lange.Ist das normal und geht das nicht schneller??

Hier der Code:
Code:
public class JFrame extends javax.swing.JFrame {
    
    /** Creates new form JFrame */
    public JFrame() {
        initComponents();
    }
    
    /** This method is called from within the constructor to
     * initialize the form.
     * WARNING: Do NOT modify this code. The content of this method is
     * always regenerated by the Form Editor.
     */
    private void initComponents() {//GEN-BEGIN:initComponents
        eingabe = new javax.swing.JTextField();
        jLabel1 = new javax.swing.JLabel();
        rechnen = new javax.swing.JButton();
        jLabel2 = new javax.swing.JLabel();
        eingabe2 = new javax.swing.JTextField();
        jLabel3 = new javax.swing.JLabel();
        jScrollPane1 = new javax.swing.JScrollPane();
        Ausgabe = new javax.swing.JTextArea();

Ausgabe.setLineWrap(true);
Ausgabe.setWrapStyleWord(true);


        getContentPane().setLayout(null);

        addWindowListener(new java.awt.event.WindowAdapter() {
            public void windowClosing(java.awt.event.WindowEvent evt) {
                exitForm(evt);
            }
        });

        getContentPane().add(eingabe);
        eingabe.setBounds(110, 30, 100, 20);

        jLabel1.setText("Primzahlen von:");
        getContentPane().add(jLabel1);
        jLabel1.setBounds(20, 30, 90, 16);

        rechnen.setText("Start");
        rechnen.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                rechnenActionPerformed(evt);
            }
        });

        getContentPane().add(rechnen);
        rechnen.setBounds(410, 30, 95, 26);

        jLabel2.setText("bis");
        getContentPane().add(jLabel2);
        jLabel2.setBounds(210, 30, 17, 20);

        getContentPane().add(eingabe2);
        eingabe2.setBounds(230, 30, 100, 20);

        jLabel3.setText("berechnen");
        getContentPane().add(jLabel3);
        jLabel3.setBounds(330, 30, 61, 20);

        jScrollPane1.setHorizontalScrollBarPolicy(javax.swing.JScrollPane.HORIZONTAL_SCROLLBAR_NEVER);
        jScrollPane1.setVerticalScrollBarPolicy(javax.swing.JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);
        jScrollPane1.setViewportView(Ausgabe);

        getContentPane().add(jScrollPane1);
        jScrollPane1.setBounds(10, 93, 520, 290);

        pack();
        java.awt.Dimension screenSize = java.awt.Toolkit.getDefaultToolkit().getScreenSize();
        setSize(new java.awt.Dimension(549, 433));
        setLocation((screenSize.width-549)/2,(screenSize.height-433)/2);
    }//GEN-END:initComponents
            
    private void rechnenActionPerformed(java.awt.event.ActionEvent evt) {//GEN-FIRST:event_rechnenActionPerformed
{
    double aktuelleZahl = Double.parseDouble(eingabe.getText());
    double endzahl = Double.parseDouble(eingabe2.getText());
    
    //Äusere Schleife
    StringBuffer s = new StringBuffer(""); 
    
    while (aktuelleZahl <= endzahl)
    {
        boolean primzahl = true;
        
        //innere Schleife
        
        double teiler = 2;
        while (teiler < aktuelleZahl)
        {
            if (aktuelleZahl % teiler == 0)
            {
                primzahl = false;
            }
            
            teiler++;
        }
        {
        if (primzahl == true)
        {
            java.text.DecimalFormat df=new java.text.DecimalFormat("0");
            s.append(df.format(aktuelleZahl)+" ");
            Ausgabe.setText(s.toString());
        }
        }
        {
           
             aktuelleZahl++;
        }
    }
    }
    
    
    
            // Add your handling code here:
    }//GEN-LAST:event_rechnenActionPerformed
    
    /** Exit the Application */
    private void exitForm(java.awt.event.WindowEvent evt) {//GEN-FIRST:event_exitForm
        System.exit(0);
    }//GEN-LAST:event_exitForm
    
    /**
     * @param args the command line arguments
     */
    public static void main(String args[]) {
        new JFrame().show();
    }
    
    
    // Variables declaration - do not modify//GEN-BEGIN:variables
    private javax.swing.JButton rechnen;
    private javax.swing.JTextArea Ausgabe;
    private javax.swing.JScrollPane jScrollPane1;
    private javax.swing.JTextField eingabe2;
    private javax.swing.JTextField eingabe;
    private javax.swing.JLabel jLabel3;
    private javax.swing.JLabel jLabel2;
    private javax.swing.JLabel jLabel1;
    // End of variables declaration//GEN-END:variables
}
 
M

Marco13

Gesperrter Benutzer
:lol: Wollen wir doch hoffen, dass es lange dauert - wenn nicht, wären praktisch alle gängigen Verschlüsselungsprogramme für'n Arsch :lol:

Es gibt ein paar SEHR naheliegende Sachen. Z.b. brauchst du erstmal nur zu testen, ob die Zahl durch 2 teilbar ist. Wenn nicht, dann kannst du danach den 'teiler' in 2er-Schritten laufen lassen (3,5,7...). Wenn man das konsequent für alle Primzahlen macht, nennt sich das "Sieb des Erathostenes" (Websuche!) (Ist aber "schwierig" zu implementieren). Und ansonsten - der Teiler muss nicht solange < aktuelleZahl erhöht werden, sondern nur solange
teiler < Math.sqrt(aktuelleZahl) + 1

Was darüber hinausgeht - da haben sich Mathematiker und Zahlentheoretiker schon SEHR SEHR SEHR viele Gedanken drüber gemacht. Fast alles davon findet man im Netz.........
 
Wildcard

Wildcard

Top Contributor
Natürlich dauert das lang, Primzahlberechnung ist ein NP Problem.
Wenn's einfach zu lösen wäre gäbe es keine Verschlüsselung :wink:
Dein Alogrithmus ist natürlich auch alles andere als Performant, aber das wird dir klar sein.
Weiterhin darfst du eine arbeitsintensive Methode nicht im gleichen Thread wie deine GUI ablaufen lassen, da die GUI dann blockiert.
 
S

SlaterB

Gast
eine allgemeine Anmerkung:
wenn du über so einen Algorithmus mit anderen redest,
dann mache doch ein kleines Konsolen-Programm mit main,

Eingabe der Zahl direkt im Quelltext, Ausgabe mit System.out.println, fertig,
in deinem obigen Code sehe ich nur GUI (setBounds..), nix was mit der Frage zu tun hat ;)
 
Wildcard

Wildcard

Top Contributor
Hier noch ein kleines Prog das halbwegs performant Primzahlen in eine Datei klopft:
Code:
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.BitSet;

public final class PrimeSieve2 {

	private static void doIt(int SIZE) throws IOException {
		long t1, t2;
		final char newLine = '\n';
		final PrintWriter writer = new PrintWriter(
				new FileWriter("results.txt"));
		BitSet set = new BitSet(SIZE);
		t1 = System.currentTimeMillis();
		set.set(0);
		set.set(1);
		writer.println(2);
		for (int i = 4; i < SIZE; i += 2) {
			set.set(i);
		}
		int end = (int) Math.sqrt(SIZE);
		for (int i = 3; i < end; i += 2) {
			if (!set.get(i)) {
				for (int j = i * i; j < SIZE; j += i) {
					set.set(j);
				}
				writer.println(i);
			}
		}
		if (end % 2 == 0)
			end++;
		for (int i = end; i < SIZE; i += 2)
			if (!set.get(i))
			{
				writer.println(i);
			}

		writer.flush();
		writer.close();
		t2 = System.currentTimeMillis();

		System.out.println((double) (t2 - t1) / 1000.0);
	}

	public final static void main(String[] args) throws IOException {

		doIt(1000000000);
	}
}
 
A

anfänger15

Bekanntes Mitglied
ok
danke an alle die mir geholfen haben.
habe jetzt mal die zeile
Code:
     while (teiler < aktuelleZahl)

durch diese ersetzt
Code:
while(teiler < Math.sqrt(aktuelleZahl) + 1 )

Das reicht erstmal für den Anfang. Es geht schon wesentlich schneller
 
Wildcard

Wildcard

Top Contributor
Du kannst es weiter verbessern in dem du alle geraden Zahlen weglässt.
 
L

Lim_Dul

Top Contributor
Wildcard hat gesagt.:
Natürlich dauert das lang, Primzahlberechnung ist ein NP Problem.
Wenn's einfach zu lösen wäre gäbe es keine Verschlüsselung :wink:
Dein Alogrithmus ist natürlich auch alles andere als Performant, aber das wird dir klar sein.
Weiterhin darfst du eine arbeitsintensive Methode nicht im gleichen Thread wie deine GUI ablaufen lassen, da die GUI dann blockiert.
Einspruch:
Der Primzahltest (Ob eine Zahl Prim ist), liegt der Klasse P. In der Wikipedia sind auch ein paar schnelle Algorithmen angegeben: http://de.wikipedia.org/wiki/Primzahltest

Vom dem Problem des Zerlegens einer Zahl in ihre Primfaktoren ist nicht bekannt, ob es in P liegt oder ob es ein NP-vollständiges Problem ist.
 
Wildcard

Wildcard

Top Contributor
Schau mal an, den AKS kannte ich noch gar nicht. ACK :wink:
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Erste Schritte TDD testen einer Methode mit injezierten Services? Allgemeine Java-Themen 12
ZeusSeinGrossopa Testen ob neuer Tag beginnt Allgemeine Java-Themen 37
S Habt ihr eine Idee wie man Serializierung testen kann..? Allgemeine Java-Themen 6
B Eclipse WebSocket programmiert, kann es leider nicht testen. Allgemeine Java-Themen 15
H OOP Testen einer Exception mit JUnit Allgemeine Java-Themen 8
perlenfischer1984 TestNG - Enum testen Allgemeine Java-Themen 1
perlenfischer1984 Testng : Funktion mit mehreren Parametern testen Allgemeine Java-Themen 5
J Best Practice Testen von protected Methoden Allgemeine Java-Themen 7
F Testen von Methoden Allgemeine Java-Themen 3
B JUnit Zufalls Operation testen Allgemeine Java-Themen 1
P Testen von UIs Allgemeine Java-Themen 2
T MEthodenauruf testen, wenn instanz erst erzeugt wird Allgemeine Java-Themen 0
M Testen von verschiedenen Produktversionen Allgemeine Java-Themen 3
T EventBus testen Allgemeine Java-Themen 1
L JUnit - automatisiertes vs. manuelles Testen? Allgemeine Java-Themen 3
R Java Performance testen Allgemeine Java-Themen 18
B Mails testen Allgemeine Java-Themen 7
A AVL-Baum - Testen ob einer vorliegt Allgemeine Java-Themen 4
aze JUnit: Testen ob bestimmte Exception nicht auftritt Allgemeine Java-Themen 18
J JUnit - werfen von Exceptions testen Allgemeine Java-Themen 17
X Testen ob ein array leer ist Allgemeine Java-Themen 6
M Server-Responds testen, Code-Redundanz Allgemeine Java-Themen 3
fastjack Unit-Testen mit Mocks Allgemeine Java-Themen 6
B FileWriter / FileReader testen / Mock-Objekt für Unit Tests? Allgemeine Java-Themen 6
H Thread Safety und Deadlocks testen Allgemeine Java-Themen 6
D Muss eine JNI Biblio testen (MAC OS X) Allgemeine Java-Themen 4
T Object auf Double, Int, String testen Allgemeine Java-Themen 5
aokai Testen von Klassen die abhängig von Stdlibs URL sind Allgemeine Java-Themen 3
S Testen einer Anwendung durch klicken von Koordinaten Allgemeine Java-Themen 7
R Testen von Applets - versch. Browser und Java Versionen? Allgemeine Java-Themen 4
V Quellcode auf "Güte" testen? Allgemeine Java-Themen 5
G JAR-DAtei testen Allgemeine Java-Themen 15
J Klasse auf Konstruktor oder Methode testen? Allgemeine Java-Themen 3
A Junit Exceptions testen Allgemeine Java-Themen 3
Z Testen welches BS benutzt wird Allgemeine Java-Themen 3
G Testen von RMI,TCP/IP, Servlets etc. Allgemeine Java-Themen 2
M Welches Linux zum Java testen? Allgemeine Java-Themen 5
P Testen mit JUnit Allgemeine Java-Themen 8
L Java6 update N bekommt neues Browser-Plugin, bitte testen. Allgemeine Java-Themen 7
G testen mit JUnit? Allgemeine Java-Themen 3
K Testen ob Methode existiert? Allgemeine Java-Themen 2
N Cashbook Management Testen Allgemeine Java-Themen 7
M String testen? Allgemeine Java-Themen 2
M String testen? Allgemeine Java-Themen 6
N auf typ testen? Allgemeine Java-Themen 3
M Programmierstill: Bitte testen anhand HTML-Tool Allgemeine Java-Themen 18
K Testen einer Klasse mit File Objekt als Parameter Allgemeine Java-Themen 6
M Bitte Testen: Mein Multi-File Editor Allgemeine Java-Themen 30
T GUI Testen Allgemeine Java-Themen 4
T GUI Testen Allgemeine Java-Themen 5
G Programm zum Testen der Striktheit von Java Allgemeine Java-Themen 9
H Laufwerk testen? Allgemeine Java-Themen 12
F Hilfe: Adjazenzmatrix mittels JUnit testen. Allgemeine Java-Themen 2
M Jemannd mit 1.4/1.3/1.2 zum Testen gesucht. Allgemeine Java-Themen 15
flashfactor Testen ob ein R/3 erreichbar bzw. noch am leben ist. Allgemeine Java-Themen 2
T Datum testen und Einsetzten Allgemeine Java-Themen 5
M Regular Expression - verschiedene Ausdrücke testen (grep | ) Allgemeine Java-Themen 5
P Dateinamen mit regulärem Ausdruck testen Allgemeine Java-Themen 9
P Dateinamen testen? Schreibrechte auf Verzeichnis testen? Allgemeine Java-Themen 8
I Primzahl Allgemeine Java-Themen 10
S Primzahl || Primfaktorzerlegung -> Eure Laufzeiten *Wen es halt interessiert* Allgemeine Java-Themen 10
S Algorithmus um nächst folgende Primzahl zu berechnen Allgemeine Java-Themen 7
B warum ist 6 eine primzahl? Allgemeine Java-Themen 11
J Threads HTTP Request (Thread) dauert lange - in Android Allgemeine Java-Themen 3
M Fasta nach Mustern durchsuchen dauert zu lange Allgemeine Java-Themen 2
T Gleiche Operation dauert teilweise sehr lange Allgemeine Java-Themen 12
H Webstart...Start dauert ewig... Allgemeine Java-Themen 5
M Wie lange dauert ein garbage collection Allgemeine Java-Themen 7
sokobus java ältere Version - das laden dauert sooo lange Allgemeine Java-Themen 3
D FileOpenDialog dauert 23 Sekunden bis zur Anzeige Allgemeine Java-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben