primzahlenrechner

Immer wieder schön sowas zu sehen, aber dann bitte in der richtigen Sektion.

Nicht schneller, sondern langsamer, aber dafür mit Spass!

;primzahlen ab 3 mittels regex

$string = "1"
For $i = 3 To 3000 Step 2
$string &= "11"
If Not StringRegExp($string, "^1?$|^(11+?)\1+$", 0) Then ;regex matched KEINE Primzahlen
ConsoleWrite('$i = ' & $i & @CRLF)
EndIf
Next

Du musst dir mal C++ anschauen Da habe ich das gleiche mit 3 Sekunden geschafft
EDIT: Wenn ich gerade nichts übersehe, dann kannste das #include <Array.au3> oben weglassen

Genau - Assembler wollte ich mir sowieso nochmal angucken Danke für die Erinnerung

Erklärung des RegEx: ^1?$|^(11+?)\1+$

^1?$ erster Teil findet Leerstring oder eine eins

^ start string
1? eine eins, null oder ein Mal
$ ende string

| oder (zweiter teil) ^(11+?)\1+$
^ start string
(11+?) Gruppe, welche 11 ein- oder mehrmals findet, diese Gruppe wird mit
\1 "gespeichert"
+ ein oder mehrmals
$ ende string

Durch das "backtracken" der RegEx-Engine entstehen bei beispielsweise 9 einsen folgende "Gruppen"
111111111
es wird mit Zweiergruppen 11 angefangen
11 11 11 11 die "übrige" eins matcht die Gruppe nicht, also backtrack mit 111
111 111 111 Gruppen matchen, also KEINE Primzahl

elf
11111111111
11 11 11 11 11 die "übrige" eins matcht die Gruppe nicht, also backtrack mit 111
111 111 111 die übrige 11 matched nicht, also backtrack mit 1111
1111 1111 die übrige 111 matched nicht, also backtrack mit 11111
11111 11111 die übrige 1 matched nicht, backtrack zuende, KEIN MATCH -> Primzahl
11111111111

Die Idee ist ja der Hammer.
Das ist ja wirklich genial

@GegX
Auf meinem i5 M560 dauerts 23s für ne Million.

@ProgrammingDonkey
Zeig mal deinen C++-Code.
Ist das der selbe Ansatz wie GegX's?
Dann wäre das ja nur gerade mal um den Faktor 7 schneller als die AutoIt-Variante.
Da wird irgendwas schief gelaufen sein - zu erwarten wäre eine deutlich höhere Beschleunigung.

Zitat von GegX

c und c++ sind einfach beide super nach an der hardware dran aber wenn dus schnell willst dann assembler und fertig

Wenn du schnelleren Assemblercode schreibst als ein aktueller C/C++-Compiler raushaut dann solltest du unbedingt mal an die Frische Luft gehen - du sast definitiv zu lange vorm PC.

Das war mein erstes und nahezu einziges C++ Script

#include <iostream>
#include <math.h>
using namespace std;


int isprime(int iNumber){
    for (int i = 2; i < sqrt(float(iNumber)); i = i+1){
        if (iNumber % i == 0){
            return 0;
        }
    }
    return true;
}


int main(){
    cout << "PRIMETEST Deluxe" << endl;
    cout << ">>>>>>>>>>>>>>>>";
    int repeat = 1;
    while (repeat){
    int start = 0;
    cout << endl << endl;
    cout << "Anfang: ";
    cin >> start;
    int end = 200000;
    cout << "Ende: ";
    cin >> end;
    cout << "Primzahlen von " << start << " bis " << end << ":" << endl << endl;
    for (int a = start; a < end+1; a = a+1){
        if (isprime(a) == 1){
            cout << a << endl;
        }
    }
    cout << endl << "Wollen sie einen neuen Durchlauf starten? [1/0]: ";
    cin >> repeat;
    }
    return 0;
}

Servus, ich war gerade dabei die Aufgabe 3 (deutsche Übersetzung) in den Project Eulers zu bewerkstelligen. Es ging um Primfaktorzerlegung, da dies ganz gut zum Thema passt würde ich gerne das Skript hier veröffentlichen. Aufgrund der hohen Zahl musste ein effizienter Algorithmus her ~ Naja

Da ich ja gerade in Java unterwegs bin, habe ich den Code von @Andy mal in einem Java-Programm untergebracht:

package primeregex;


import java.util.regex.Pattern;
import java.util.regex.Matcher;


/**
 *
 * @author Xoria
 */
public class Primeregex {


    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        StringBuilder primeString = new StringBuilder("1");
        Pattern primePattern = Pattern.compile("^1?$|^(11+?)\\1+$");
        for(int i = 3; i < 3000; i+=2){
            primeString.append("11");
            Matcher primeMatcher = primePattern.matcher(primeString.toString());
            if(!primeMatcher.matches()){
                System.out.println("i = " + i);
            }
        }
    }

}

Falls sich jemand wundert, warum in Zeile 17 das "\" durch "\\" ersetzt wurde: In Java muss das "\" um als "\" zu funktionieren auch ausgeklammert werden.
Bei 10.000 Primzahlen schafft er es innerhalb von - sage und schreibe - 6 Sekunden...

Zitat von AspirinJunkie

Dann wäre das ja nur gerade mal um den Faktor 7 schneller als die AutoIt-Variante.

Tja, auch der beste und schnellste Compiler kann aus Sch**** kein Gold machen.
Ich bin allerdings davon überzeugt, dass die Jungs und Mädels in Santa Clara schon (wenn nicht bereits implementiert) Code vor dem compilieren analysieren um herauszufinden was der Programmierer BEABSICHTIGT!
Dabei würde bei der Analyse das o.g. Programms festgestellt, dass mit unveränderlichen Daten (Zahlen) gearbeitet wird und dass die durch 2 teilbaren Zahlen niemals in die "Zielgruppe" passen. Somit würde der Compiler den Code so weit optimieren, dass aus

for (int i = 2; i < sqrt(float(iNumber)); i = i+1){

eben

for (int i = 1; i < sqrt(float(iNumber)); i = i+2){

wird. Faktor 2 in der Geschwindigkeit, voila!

Ich hatte neulich einen Bericht dahingehend gelesen, dass diese "optimierten" Codestellen im orginalen Quellcode ersetzt und markiert wurden. Einige gestandene Programmierer hatten nicht schlecht gestaunt, wie viel von ihrem Code "wegoptimiert" werden KANN!
Daher auch die grundlegende Direktive, möglichst wenig selbst zu programmieren, sondern bereits bestehende (und somit OPTIMIERTE! ) Bibliotheken zu verwenden.
Das Problem tut sich aber auf, dass es Bibliotheken gibt, die irgendjemand irgendwann erstellt, aber niemand sonst sich die Mühe gemacht hat, diese zu optimieren! Aber was solls, funktioniert doch!!!
Von daher befindet sich der Kollege ProgrammingDonkey in der schönen Lage, auch "was solls, funktioniert doch!"

Zitat von AspirinJunkie

Da wird irgendwas schief gelaufen sein - zu erwarten wäre eine deutlich höhere Beschleunigung.

unter dieses Statement zu setzen

Optimierung sollte halt immer auf Algorithmenebene beginnen.
In dem Fall wäre es erst einmal sinnvoll den Algorithmus von GegX zu übertragen.
Das wurde in deinem C++-Programm nämlich nicht gemacht.

Das Primzahlen nur ungerade sein können (außer der 2) hat Andy dir bereits erzählt.

In deinem Programm wird zur Überprüfung auf eine Primzahl durch alle natürlichen Zahlen kleiner Wurzel der zu prüfenden Zahlen geteilt. Es geht aber noch deutlich effektiver: Jede natürliche Zahl ist durch eine Kombination von Primzahlen teilbar (siehe Primfaktorzerlegung). Wenn sie selbst eine Primzahl ist, so ist ihr Primfaktor schlicht die Zahl selbst. GegX' nutzt das in seinem Skript um die Zahl der nötigen Vergleiche nochmals deutlich zu reduzieren: indem er die Zahl nur gegen die bisher gefunden Primzahlen checkt (und das auch nur bis Wurzel(n)). Somit kann er die Anzahl der nötigen Vergleiche drastisch verringern.
Es wäre also durchaus clever die Primzahlen zwischenzuspeichern. Da du C++ verwendest, suchst du also nach einer Datenstruktur bei der dynamisch Elemente ans Ende hinzugefügt werden können und die schnell durchiteriert werden kann. Mein Vorschlag hierfür wäre die std::deque.

Das was dem Programm den Rest in Sachen Performance gibt, ist die Ausgabe aller Zahlen auf die Konsole. Entferne mal zum Spaß die couts und lass dir nur die letzte Zahl ausgeben - es sollte nun drastisch schneller laufen

GegX:
Dein Algorithmus hat eine Ausführungszeit von 25 Sekunden bei mir. Ich habe mal versucht mithilfe des Sieb des Eratosthenes die benötigte Zeit zu verringert. Alle Primzahlen von 2 bis 1000000 werden bei mir in 18~19 Sekunden ermittelt. Da geht bestimmt noch mehr:

@Make-Grafik
Dein Script braucht bei mir sogar nur 12s. Meine Variante in AutoIt umgesetzt und verbessert hingegen braucht 104s
Das ist erstmal beeindruckend
Mal sehen, ob wir das noch schneller hinkriegen

Klar geht das schneller: Alle Primzahlen bis 1'000'000 in 1,5 Sekunden

Genial
Allerdings verstehe ich deinen Code nicht ganz, und bitte dich darum mal eine Erklärung dazu zu verfassen
Und noch eine Idee:

Ich habe mich nun an die gleiche Technik angelehnt, wie @Make-Grafik, allerdings funktioniert das ganze nur sehr langsam:

Wie kann ich da (viel) mehr Zeit sparen?