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

[anfänger15]

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:

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
}

 

[Marco13]

: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]

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.

 

[SlaterB]

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]

Hier noch ein kleines Prog das halbwegs performant Primzahlen in eine Datei klopft:

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

 

[anfänger15]

ok
danke an alle die mir geholfen haben.
habe jetzt mal die zeile

     while (teiler < aktuelleZahl)

durch diese ersetzt

while(teiler < Math.sqrt(aktuelleZahl) + 1 )

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

 

[Wildcard]

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

 

[Lim_Dul]

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]

Schau mal an, den AKS kannte ich noch gar nicht. ACK :wink: