Kuerzbare Brueche

[Is@@c]

Hi,
ich hab versucht was zu coden, dass mir die Anzahl der kuerzbaren Brueche bis eine million liefert, also von 2/3 bis 1000000 / 999999 alles prüft, hab mir was zurecht gebastelt, dass ist aber übel langsam weil holzfäller style. wär für vorschläge dankbar, wie ich das schneller hinkrieg



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

void main()
{

#define LIMIT 100000
bool primzahlen[LIMIT] = {false, false};
int i, j, p, k = 0, zaehler = 0, kuerzbarebrueche = 0;
int * prim;
double ergebnis, gesamtzahl = LIMIT;

for(i = 2; i < LIMIT; i++)
{
primzahlen[i] = true;
}

for(i = 2; i < sqrt(LIMIT); i++)
{
if(primzahlen[i])
{
for(j = i+i; j < LIMIT; j += i)
{
primzahlen[j] = false;
}
}
}

for(i = 0; i < LIMIT; i++)
{
if(primzahlen[i])
{
zaehler++;
}
}

prim = new int[zaehler];

for(i = 0; i < LIMIT; i++)
{
if(primzahlen[i])
{
prim[k] = i;
k++;
}
}

for(i = 2; i <= LIMIT; i++)
{
for(j = 2; j <= LIMIT; j++)
{
if(i < j)
{
for(p = 0; (p < zaehler) && (prim[p] <= i); p++)
{
if((i % prim[p]) == 0)
{
if((j % prim[p]) == 0)
{
kuerzbarebrueche++;
break;

}
}

}
}

if(j < i)
{
for(p = 0; (p < zaehler) && (prim[p] <= j); p++)
{
if((i % prim[p]) == 0)
{
if((j % prim[p]) == 0)
{
kuerzbarebrueche++;
break;
}
}

}
}
}

}

ergebnis = kuerzbarebrueche;

cout<<&quot;Es gibt &quot;<<kuerzbarebrueche<<&quot; kuerzbare Brueche im bereich von 1 - &quot;<<gesamtzahl<<&quot; , daraus ergibt sich eine Wahrscheinlichkeit von &quot;<<ergebnis / ((gesamtzahl * gesamtzahl) - (2 * gesamtzahl))<<&quot;\n&quot;;


}






thx
Is@@c

[xOOn]

wenn ich mich noch recht an den mathe unterricht erinnere dann funkt das folgendermassen!

also man splittet beide nummern auf

90/100 = (2 * 3 * 3 * 5) / (2 * 2 * 5 * 5)
und dann loescht man die welche identisch sind (2 und 5) also (3 * 3)/ (2 * 5)

oder man dividiert beide dur den ggT (groessten gemeinsamen Teiler), wie man den genau rauskriegt weiss ich nichtmehr :(, aber einer der unistudenten wird das wohl nich wissen :P :P :P

[Is@@c]

Hilft mir leider noch nicht ganz weiter :(

[sami]

den ggT ermittelt man genau so, indem man die zahlen in die sogenannten primfaktoren (eben dieses 2 * 3 * 3 * 5) zerteilt und dann all diejenigen raus nimmt, die in beiden vorkommen.
um also zu ermitteln, ob ein bruch teilbar ist, müssen die primfaktoren verglichen werden, bis entweder 2 übereinstimmende gefunden wurden oder keine mehr da sind.