Nachkommastellen

[camper]

wenn du a mod b kennst, ist (a-1) mod b trivial.

[volkard]

wenn 2^15 mod 100==86, dann 2^15 mod 100 - 1 == 85.

[Ölscheich]

Das mit dem 1 abziehen ist mir jetzt absolut klar! Vielen Dank!
Doch ich bin ein wenig über

volkard schrieb:

wenn 2^15 mod 100==86, dann 2^15 mod 100 - 1 == 85.

verwundert. Mein Rechner sagt dazu 68. Aber das ist dann wohl nur ein Zahlendreher oder?
Allerdings verstehe ich nicht wie man auf den Rest kommt.
Klar wenn es einen Rest gibt kommt bei a mod b ein Rest raus der ungleich a ist.
Aber wie kann ich feststellen wie hoch der Rest ist.
Sorry für meinen Fragen und mein nicht vorhandenes Verständnis!

[volkard]

ja, zahlendreher. habs im kopf gemacht und verdreht.

Aber wie kann ich feststellen wie hoch der Rest ist.

der rest, der bei a/b rauskommt, ist doch genau a mod b.

oder versteh ich dir frage nicht? dann mach beispiele.

[Ölscheich]

volkard schrieb:

ich rechne mal 2^15 mod 100 aus.
2^1 == 2
(quadrieren)
2^2 == 4
(modden)
2^2==4
(quadrieren)
2^4 == 16
(modden)
2^4 == 16
(quadrieren)
2^8 == 256
(modden)
2^8 == 56

Aber der Rest ist natürlich nicht 56 sondern 68.
Wie komme ich auf 68?

[volkard]

Ölscheich schrieb:

volkard schrieb:

ich rechne mal 2^15 mod 100 aus.
2^1 == 2
(quadrieren)
2^2 == 4
(modden)
2^2==4
(quadrieren)
2^4 == 16
(modden)
2^4 == 16
(quadrieren)
2^8 == 256
(modden)
2^8 == 56

Aber der Rest ist natürlich nicht 56 sondern 68.
Wie komme ich auf 68?

ich muss noch rechnen
(alles mod 100)
2^15 = 2^8 * 2^4 * 2^2 * 2^1

= 56 * 16 * 4 * 2
= 96 * 4 * 2
= 84 * 2
= 64

[Ölscheich]

volkard schrieb:

Ölscheich schrieb:

volkard schrieb:

ich rechne mal 2^15 mod 100 aus.
2^1 == 2
(quadrieren)
2^2 == 4
(modden)
2^2==4
(quadrieren)
2^4 == 16
(modden)
2^4 == 16
(quadrieren)
2^8 == 256
(modden)
2^8 == 56

Aber der Rest ist natürlich nicht 56 sondern 68.
Wie komme ich auf 68?

ich muss noch rechnen
(alles mod 100)
2^15 = 2^8 * 2^4 * 2^2 * 2^1

= 56 * 16 * 4 * 2
= 96 * 4 * 2
= 84 * 2
= 64

Also vielen Dank für die Mühe die ihr euch gemacht habt, aber ich hab das Programm geschrieben(auch wenn ihr über die effizienz und struktur schmunzeln werdet) und mit Testzahlen arbeitet es einwandfrei aber es liefert mir keine einzige Wieferich Primzahl.
Hier ist der Code:

#include "stdafx.h"
#include "math.h"

int exponent,h,i,letztesgesetztesarray,zahl2,mod,x,n,faktor[1000];

int main()
{
for(n=3;n<3600;n++)
{
i=0;
mod=1;
zahl2=n*n;
exponent=n-1;
h=2;
while(pow(2,h)<zahl2)
{
h=h+1;
}
while(exponent>0)
{
faktor[i]=pow(2,h);
i++;
exponent=exponent-h;
if(h=exponent)
{
h=exponent;
}
}

letztesgesetztesarray=i-1;
for(x=letztesgesetztesarray;x>=0;x--)
{
mod=mod*fmod(faktor[x],zahl2);
}
mod=mod%zahl2;
if(mod==1)
{

	printf("%i\n",n);

}
}
	return 0;
}

[borg]

Ölscheich schrieb:

auch wenn ihr über die effizienz und struktur schmunzeln werdet

welche struktur?

#include <iostream>

int nextPrim( int p )
{
    return Nächste Primzahl nach p; // <- pseudocode, bitte implementieren!
}

bool wieferichPrim( int p )
{
    return ( 2^(p-1) Modulo p*p ) == 1; // <- pseudocode, bitte implementieren!
}

int main( )
{
    int prim = 3;
    while( prim < 3600 )
    {
        if( wieferichPrim( prim ) )
            std::cout << prim << " ist eine Wieferich-Primzahl!";
        prim = nextPrime( prim );
    }
}

ich geb dir mal einen strukturierten rahmen, jetzt brauchst du nur noch Volkards trick implementieren und dir überlegen wie du an die nächste primzahl kommst

edit: oh, schreibst du in c oder cpp? wenn du c willst musst du die cout zeile austauschen durch "printf( "%i ist eine Wieferich-Primzahl!", prim );" und die include zeile durch "#include <stdio.h>".

[Ölscheich]

Ich hab es in das Gerüst eingebaut, aber es funktioniert immernoch nicht...
wenn ich für exponent und zahl2 Werte eingeben rechnet er korrekt, aber er gibt mir keine Einzige Wieferich Primzahl
Bitte helft mir und sagt mir wo mein Denkfehler liegt!

#include "stdafx.h"
#include "math.h"
int nextPrim( int p ) 
{ 
	int z=0;
	int h,keineprim=0;
	while(z==0)
	{
		p=p+2;
		h=2;
		keineprim=0;
		while(p>h*2-1)
		{
			if(p%h==0)
			{
			keineprim=1;
			}
			h=h+1;
		}
		if (keineprim==0)
		{
			z=1;
		}	
	}

    return(p);
} 

bool wieferichPrim( int p ) 
{
int exponent,h,i,letztesgesetztesarray,zahl2,mod,x;
double faktor[1000];
i=0;
mod=1;
zahl2=p*p;
exponent=p-1;
h=2;
while(pow(2,h)<zahl2)
{
h=h+1;
}
while(exponent>0)
{
faktor[i]=pow(2,h);
i++;
exponent=exponent-h;
if(h=exponent)
{
h=exponent;
}
}

letztesgesetztesarray=i-1;
for(x=letztesgesetztesarray;x>=0;x--)
{
mod=mod*fmod(faktor[x],zahl2);
}
mod=mod%zahl2;
if(mod==1)
{
	return 1;
}
return 0;

} 

int main() 
{ 
    int prim = 3;
    while( prim < 3600 ) 
    { 

        if( wieferichPrim( prim ) ) 
           printf( "%i ist eine Wieferich-Primzahl!\n", prim );

        prim = nextPrim( prim ); 

    } 
	return 0;
}

[borg]

#include <stdio.h>

int nextPrim( int p )
{
    int z=0;
    int h,keineprim=0;
    while(z==0)
    {
        p=p+2;
        h=2;
        keineprim=0;
        while(p>h*2-1)
        {
            if(p%h==0)
            {
            keineprim=1;
            }
            h=h+1;
        }
        if (keineprim==0)
        {
            z=1;
        }   
    }
    return p; 
}

bool wieferichPrim( int p )
{
    int result = 1;
    int i;
    for( i = 0; i < p-1; i++ )
        result = ( result * 2 ) % ( p*p );

    return result == 1;
}

int main( )
{
    int prim = 3;
    while( prim < 3600 )
    {
        if( wieferichPrim( prim ) )
            printf( "%i ist eine Wieferich-Primzahl!\n", prim );
        prim = nextPrim( prim );
    }
}

schade das du es nicht hinbekommen hast. deine primzahlfunktion funktioniert aber, ich hab sie einfach mal übernommen, auch wenn sie nicht die flotteste ist
also auf meinem laptop(celeron 800mhz) findet er 2 wieferich-primzahlen: 1093 und 3511.
dauert so ca. 2 sekunden.

ps: ich hätte ja deine lösung gern korrigiert, leider versteh ich sie nicht