Brauche Hilfe für Primzahlenrechner

[KPvC]

Hallo,

ich hab mal eine kleine Frage:
Ich habe ein Programm mit C geschrieben, welches Zahlen in ihre Primzahlfaktoren zerlegt. (das läuft auch soweit ganz gut)
Also gibt man z.B "25" ein, so wird "25 = 1 * 5 * 5" ausgegeben.
Gibt man z.B "17" ein, so wird "17 ist ein Primzahl ausgegeben".
Ich bin totaler Anfänger auf dem Gebiet C-Programmierung und soll das Programm zeitotimieren. Ich habe kein Plan wie ich das Ding schneller machen kann ;-(
Vielleicht kann mir ja einer von euch einen Rat geben.

Hier der Quelltext:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    while (1)
    {
        unsigned long long i,c,kleinster_Teiler=2;
        time_t startzeit,endzeit;
        float laufzeit;

        printf("\nBitte geben Sie eine Berechnungzahl ein:  ");
        scanf("%I64u",&i);
        c=i;
        startzeit=clock(1);
        while (kleinster_Teiler<i)
        {
            if (c%kleinster_Teiler==0)
            {
                printf("%I64u = 1 * ",c);
                kleinster_Teiler=i;
            }
            else
            {
                kleinster_Teiler++;
            }
        }
        kleinster_Teiler=2;
        while (i>1)
        {
            if (i%kleinster_Teiler==0)
            {
                printf("%I64u",kleinster_Teiler);
                i=i/kleinster_Teiler;
                if (i>1)
                    printf(" * ");

            }
            else
                kleinster_Teiler++;
        }
        endzeit=clock(2);
        if (kleinster_Teiler==c)
        {
            printf(" ist eine Primzahl");
        }
        laufzeit=(endzeit-startzeit)/1000;
        printf("\nLaufzeit: %f Sekunden\n",laufzeit);
    }

    return 0;
}

 

[Jennesta]

Es wäre sicher schonmal hilfreich, wenn du den Quelltext ordentlich formatieren und zwischen [ cpp ] .. [ /cpp ] tags schreiben würdest. Weil so werden das sicher weniger Leute lesen.

Gruß

 

[Vereth]

1. Der größte Teiler einer Zahl n kann nicht größer sein als WURZEL, du kannst also die Obergrenze deiner Schleife jeweils dynamisch anpassen.
2. Sobald du die 2 als Teiler ausgeschlossen hast, kannst du die Schrittweite auf 2 erhöhen.

Und zum vorzeitigen Abbruch einer Schleife verwendet man die break-Anweisung.

 

[mc_gulasch]

Die Optimierung von Primzahltests ist eine der schwierigsten Aufgaben der Mathematik derzeit. Es gibt auch schon viele Methoden dazu. Es stellt sich die Frage, ob du die Primzahlenfaktorisierung benötigst, oder "nur" die Tatsache, ob es sich bei der Zahl um eine Primzahl handelt. Für letzteres ist der AKS-Primzahlentest meines Wissens derzeit der schnellste, für die Zerlegung gibt es derzeit noch kein "schnelles", also in polynomieller Laufzeit laufendes, Programm. Das ist auch gut so, sonst hätten wir ein kleines Sicherheitsproblem

Ansonsten gibt es noch eine Reihe an zahlentheoretischen Eigenschaften, mit denen man ausschließen kann, ob eine Zahl prim ist oder nicht:
- Quersumme durch 3 teilbar => Zahl durch 3 teilbar
- Endung auf 5 oder 0 => durch 5 teilbar
... findest du alles hier

Und schau dir mal den Euklidischen Algorithmus und das Faktorisierungsverfahren von Fermat an. Vielleicht hilft dir das weiter.

[Klugscheiss]
Wenn Du alle Primfaktoren angeben sollst, dann ist "1" nicht dabei, da "1" per definitionem keine Primzahl ist
[/Klugscheiss]