Mein erstes Programm!! [Prime95 Konkurrenz xD]

[sh4w]

So hab mal mein erstes halbwegs nützliches Programm gebastelt!

Es ist ein Programm, dass nach eingaber einer Zahl (die übrigens bis zu 18 trillionen groß sein darf ^^) prüft ob eine Zahl eine Primzahl ist oder nicht,
falls nicht, zeigt es den kleinstmöglichen Teiler der Zahl!

Man kann es aber auch als CPU Stresstest Tool benutzen! XD
Ne 9 stellige Primzahl schafft mein Quad Core in ca. 10 sekunden...und ja..das Programm nutzt irgendwie alle Cores aus...fragt mich nicht wieso..^^

Bugs die mir schon bekannt sind, ich aber zu blöd bin sie zu fixen:
-falls man buchstaben eingibt wenn man eigentlich Zahlen eingeben sollte, schmiert das Prog ab ^^

Feedback zum Code und Verbesserungsvorschläge sowie weitere Anregungen was an was ich mich in Zukunft versuchen soll erwünscht! ^^

Links:
http://home.arcor.de/sh4w0r/Prime.cpp <- Source
http://home.arcor.de/sh4w0r/Prime.exe <- Prog

[N4wuko]

Soweit ich weiß, kriegste mit der BigInteger Klasse so große Zahlen hin, wie du magst.
Jedenfalls is das in Java so
Müsst in C das selbe sein.

[blackberry]

@sh4w

if(divisor > max || divisor > prime)

... ergibt keinen richtigen Sinn!
Wenn ich davon ausgehe, dass max mit 0xFFFFFFFFFFFFFFFF gefüllt ist (maximaler Wert für einen unsigned long long int), dann ist if (divisor > max) nicht möglich, da nach einem Überlauf dein divisor zu 0 wird (was dein Programm nicht bemerkt, es aber beim nächsten Teilen, aufgrund einer Division durch 0, zum Absturz bringen wird).

Es würde auch soetwas reichen:

if(divisor > (max - 1) || divisor >= (prime / 2 + 1))

Ansonsten werden ja Zahlen gecheckt, die aus dem rein logischen schon keine Teiler mehr sein können - wenn ein Teiler größer ist als die Hälfte der Zahl, dann kommt in der Regel nie ein Ergebnis aus dem Bereich der natürlichen Zahlen raus.


mfG. BlackBerry

[Sirect]

Also wenn ich ne 9-Stellige Zahl eingebe dann ist die Direkt ausgerechnet, gebe ich eine Extrem lange Zahl ein dann startet das Programm immer wieder,fragt mich, und das immer wieder...

[sh4w]

@sh4w

if(divisor > max || divisor > prime)

... ergibt keinen richtigen Sinn!
Wenn ich davon ausgehe, dass max mit 0xFFFFFFFFFFFFFFFF gefüllt ist (maximaler Wert für einen unsigned long long int), dann ist if (divisor > max) nicht möglich, da nach einem Überlauf dein divisor zu 0 wird (was dein Programm nicht bemerkt, es aber beim nächsten Teilen, aufgrund einer Division durch 0, zum Absturz bringen wird).

Es würde auch soetwas reichen:

if(divisor > (max - 1) || divisor >= (prime / 2 + 1))

Ansonsten werden ja Zahlen gecheckt, die aus dem rein logischen schon keine Teiler mehr sein können - wenn ein Teiler größer ist als die Hälfte der Zahl, dann kommt in der Regel nie ein Ergebnis aus dem Bereich der natürlichen Zahlen raus.


mfG. BlackBerry

Danke für den Tipp!! ^___^
Zahlen werden jetzt um einiges schneller ausgerechnet ^^

Also wenn ich ne 9-Stellige Zahl eingebe dann ist die Direkt ausgerechnet, gebe ich eine Extrem lange Zahl ein dann startet das Programm immer wieder,fragt mich, und das immer wieder...

Das lieget daran dass die meisten großen zahlen eienen teiler von 2-10 haben, diese werden dann natürlich schnell herausgefunden, da das programm alle teiler von 2 - 9 trillionen (statt 18 trillionen dank blackberry ^^) ausprobiert... D.h. wenn eine Zahl einen niedrigen teiler hat, wird diese sehr schnell berechnet =)

[cobhc]

Was ich mir noch überlegt habe:
1.

if(divisor > (max - 1) || divisor >= (prime / 3 + 1))

nach prime/3 kommt ja nur noch eine natürliche Zahl als Teiler: Prime/2. Diese ist aber immer x.5 also unerheblich für Primzahlen, oder man hat eine gerade Zahl eingegeben. Die sind aber durch 2 Teilbar und fallen vorher weg, oder irre ich mich da?
und 2.

if(divisor < 3)
        divisor = divisor + 1LL;
        else
        divisor = divisor + 2LL;

Wenn eine Zahl durch 2,4,6,8,10 etc teilbar ist, ist sie durch 2 Teilbar, fällt also schon vorher weg. Wenn meine Überlegungen stimmen würde es also ausreichen durch 3,5,7,9 etc zu teilen.
Wenn ich irgendwo einen Denkfehler habe, sagt Bescheid.

[-[RiDER]-]

Hi

Was ich mir noch überlegt habe:

if(divisor > (max - 1) || divisor >= (prime / 3 + 1))

nach prime/3 kommt ja nur noch eine natürliche Zahl als Teiler: Prime/2. Diese ist aber immer x.5 also unerheblich für Primzahlen, oder man hat eine gerade Zahl eingegeben. Die sind aber durch 2 Teilbar und fallen vorher weg, oder irre ich mich da?

Ich kann keine immanente mathematische Substanz in diesem Absatz finden.
Entweder verstehe ich Dich falsch, oder Du irrst Dich.

Wenn eine Zahl durch 2,4,6,8,10 etc teilbar ist, ist sie durch 2 Teilbar, fällt also schon vorher weg. Wenn meine Überlegungen stimmen würde es also ausreichen durch 3,5,7,9 etc zu teilen.

Eine Primzahl ist eine Zahl, die nur durch 1 und durch sich selbst teilbar ist.
D.h. dass genau keine Division aufgehen darf!

Du versuchst quasi alle Primzahlen auszurechnen (die Neun ist übrigens keine!) und das ist ein größerer Aufwand.

Wenn Du (ohne Rechnen) vorhersagen könntest, durch welche Zahlen sich eine Zahl nicht teilen lässt, würdest Du die Mathematik revolutionieren, denn dass hat bisher noch keiner geschafft.

Oder meinst Du das "streichen" von Nicht-Primzahlen?
Also alle Zahlen der Zweierreihe aussortieren (bleiben 3, 5, 7, 9, 11, 13, 15, 17, 19...), dann alle Zahlen der Dreierreihe (bleiben 5, 7, 11, 13, 17, 19...), alle der Fünferreihe (Viererreihe fällt weg, weil durch Zweierreihe bereits aussortiert, bleiben 7, 11, 13, 17, 19...).
Am Ende bleibt eine riesige Liste von allen Primzahlen, die kleiner (oder im Idealfall: gleich) sind als die gewünschte Zahl.
Ist programmiertechnisch aber nur umständlich zu lösen (z.B. über verkettete Listen).

GreetZ RiDER

[cobhc]

primenew = prime % divisor;
              
      if(primenew == 0LL)
      {
        cout<<"\n\n\nThats not a prime number...\n";
        cout<<"Divisor found: " <<divisor <<"\n\n";
        break;
      }
      else
      {
        if(divisor > (max - 1) || divisor >= (prime / 2 + 1))
        {
          cout<<"\n\n\nPrime number found!!\n\n";
          break;
        }
        
        divisor = divisor + 1LL;

Das Programm teilt eine Zahl prime solange durch den divisor, bis der divisor entweder größer als die Hälfte der Zahl ist, oder er eine restlose division durchführen kann, richtig?
Also durch 1,2,3,4,...,X/2+1.
Wenn nun aber X/2 keine Natürliche Zahl ergibt, dann kann auch X/4, X/6 etc keine natürliche Zahl mehr sein, also lohnt es sich nicht diese Zahlen zu berechnen. Deshalb

divisor = divisor + 2LL;

Das Programm soll ja nur herausfinden ob die Zahl X eine Primzahl ist.

Über das andere würde ich gerne noch mal nachdenken, was ich mir dabei gedacht habe :S

[FormChanger]

toll - was kann man dazu noch sagen?

[westdaman]

Das kleine Buchstaben Problem sollte mit "FormatException" gelöst sein. So ist das in c#