Modulo und Doubles

[davie]

ohne auf formales genauer einzugehen

benpicco schrieb:

Ich will das ganze auf Doubles umstellen (jaja, Große Primzahlen sind doch was feines :D)

wenn du überprüfen willst, ob große zahlen (als double) prim sind, hast du ein problem: große doubles sind nicht mehr auf einer genau.

[life]

stell doch einfach auf long long (int64) um. Dann kannste ja mal mit deinem prog testen, ob z.B. 2305843009213693951 eine Primzahl ist >_<

[benpicco]

Wow, was nicht alles geht...
2305843009213693951 hat gute Chancen eine Primzahl zu sein, er rechnet jetzt schon eine ganze Weile und hat noch nichts gefunden.
(Mist, mein PC ist gerade im Begriff, sich aufzuhängen!)
Edit: Das Program meint jetzt 2305843009213693951=2*2*2*2*2*2*2*2*6361*69431*20394401. So wirklich glauben tue ich das nicht... (ich hab alle doubles mit unsigned long long ersetzt)
Villeicht ist die Zahl doch zu groß...

[life]

also der Faktor 2 sollte definitiv nicht drin sein

[c.rackwitz]

2**61-1 ist eine mersenneprimzahl.

im uebrigen ist in der "gleichung" eine differenz von 255.

[benpicco]

c.rackwitz schrieb:

2**61-1 ist eine mersenneprimzahl.

Das erklärt wohl einiges. Wenn ich Doubles benutze, kommt noch ziemlich langer Rechenzeit 2^61 raus...
Von long long hätte ich da aber eine höhere Genauigkeit erwartet, wenn sie genausoviel Platz brauchen, wie doubles (64 bit?), oder könnte das am fmod Befehl liegen, der scheinbar für doubles ausgelegt ist?
Oder hab ich in meinem code einfach mist gebaut?

#include <cstdlib>
#include <iostream>
#include <math.h>

using namespace std;
typedef unsigned int long long numTyp;

numTyp PrimCheck(numTyp number);
void PrimShow(numTyp number);

numTyp PrimCheck(numTyp number)
{
    numTyp teil=0;
    numTyp x,to;
    if(!(fmod(number,2)) && number !=2)
    teil=2;
    to=sqrt(number)+1;
    for(x=3; x<to; x=x+2)
    {
             if(!(fmod(number,x)))
             {
                            teil=x;
                            break;
             }
    }
    return teil;
}
void PrimShow(numTyp number)
{
     if(!(PrimCheck(number)))
     cout << number <<endl;
     if(!(fmod(number,2)))
     number++;
     do
     {
                 if(!(PrimCheck(number)))
                 cout << number <<endl;
                 number=number+2;
     }
     while(1);
}

int main()
{
    numTyp zahl=23;
    numTyp teiler=0;
    cout << "***Primzahlen***\n";
    cout << "(Geben sie 0 ein um alle Primzahlen ab einer Zahl ihrer Wahl anzuzeigen)";
    while(1)
    {
    cout << "\nZahl eigeben:";
    cin >> zahl;
    if(zahl)
    {
    teiler=PrimCheck(zahl);
    if(teiler==0)
    cout << "Primzahl\n";
    else
    {
        cout << "Keine Primzahl\n"; 
        cout << zahl << "=";
        while(teiler=PrimCheck(zahl))
        {    
             cout<<teiler<<"*";    
             zahl=zahl/teiler;                     
        }
        cout<<zahl;
    }
    }
    else
    {
        cout << "Alle Primzahlen ab ";
        cin >> zahl;
        PrimShow(zahl);
    }  

    }
    //system("PAUSE");
    return EXIT_SUCCESS;
}

Naja, wenn das mit dieser Zahl funktionier, bin ich ganz zufrieden

[life]

benutz doch einfach modulo.. dann sollte es auch klappen..

[CStoll]

fmod ist auf Gleitkomma-Zahlen ausgelegt - wenn du dort große long long reingibst, nützt dir deren höhere Genauigkeit nichts. (aber für long long klappt afaik der %-Operator).

PS: Um die angegebene Zahl zu überprüfen, benötigst du vermutlich einen eigenen Datentyp "unlimited_int"

[benpicco]

Ah, % funktioniert also nur mit int

CStoll schrieb:

PS: Um die angegebene Zahl zu überprüfen, benötigst du vermutlich einen eigenen Datentyp "unlimited_int"

Und dazu noch eine CPU mit unlimeted_MHZ ^^

[life]

afaik funktionert % mit allen Ganzzahltypen (char, short, int, long, long long)..