013
24.10.2003, 18:02 Uhr
NemoEimi
|
Hallo,
hier mal meine Lösung für dieses Rätsel, natürlich in Java  :
| C++: |
//Dieses Programm findet alle Zahlenpaare der Form (n, n+1) zwischen eins und einer frei wählbaren Zahl < 2^31, für die n und n+1 die gleiche Teilersumme haben
//Dabei ist die obere Grenze des Suchbereiches als Kommandozeilenparameter zu übergeben
public class tsum {
public static int prim_teiler(int n) {
if (n%2==0) return(2);
for (int i = 3; i * i <= n; i = i + 2)
if (n%i==0) return(i);
return(n);
}
public static int teilersumme(int n) {
int summe = 1;
//wir haben uns überlegt, daß für teilerfremde Zahlen m und n
//teilersumme(m*n) = teilersumme(m)*teilersumme(n) ist
while (n > 1) {
int p = prim_teiler(n);
int neuer_faktor = 1; int pow = 1;
while (n%p == 0) {
pow = pow * p;
neuer_faktor = neuer_faktor + pow;
n = n / p;
}
summe = summe * neuer_faktor;
}
return(summe);
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int letzte_summe = 1;
for (int i = 2; i < n; i++) {
int aktuelle_summe = teilersumme(i);
if (letzte_summe == aktuelle_summe) System.out.println((i - 1) + " " + i + " " + letzte_summe);
letzte_summe = aktuelle_summe;
}
}
}
|
Grüße,
Nemo
P.S.: Wenn ich diesen Java-Code eins-zu-eins nach C++ übertrage, und dann mit gcc zweistufig compiliere (also den Compiler Profilerinformation auswerten lasse), dann kriege ich drei Prozent Geschwindigkeitsvorsprung für die C++ - Version hin. Falls jemand noch nette Mikrooptimierungen sieht, die da einen größeren Unterschied erzeugen (bin im Finden solcher Optimierungen nicht gut), wäre ich interessiert.
Dieser Post wurde am 24.10.2003 um 18:22 Uhr von NemoEimi editiert. |
)
