Bloodsurfer
Gentoo-User
Hallo Leute.
Ich versuche gerade ein eigentlich simples Problem zu lösen - ich will eine Zahl n in zwei Quadratzahlen zerlegen, sofern möglich.
In etwa so:
Die Zahl 9 ist zerlegbar in 3^2 + 0^2.
Die Zahl 10 ist zerlegbar in 3^2 + 1^2.
Ne kleine Lösung hab ich schnell gebastelt:
Das funktioniert mit kleinen Zahlen einwandfrei, aber es ist zugegebenermaßen sehr ineffizient und bei grossen Zahlen, wie z.B. 72003446399952, kann man es vergessen, würde ja stundenlang laufen.
Daher meine Frage: Hat jemand einen Vorschlag, wie ich das effizienter gestalten könnte um auch bei sehr grossen Zahlen zu einem Ergebnis zu kommen?
Ich versuche gerade ein eigentlich simples Problem zu lösen - ich will eine Zahl n in zwei Quadratzahlen zerlegen, sofern möglich.
In etwa so:
Die Zahl 9 ist zerlegbar in 3^2 + 0^2.
Die Zahl 10 ist zerlegbar in 3^2 + 1^2.
Ne kleine Lösung hab ich schnell gebastelt:
Code:
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char** argv) {
if (argc != 2) {
printf("Bitte genau eine Zahl als Argument eingeben!\n");
return 1;
}
long n=atol(argv[1]); //wandelt erstes Argument der Kommandozeile in Zahl um
long qz1=0;
long qz2=0;
//suche erste Quadratzahl die ein Teil von n ist
while ((qz1*qz1)<=n) {
//suche zweite Zahl
while (((qz1*qz1)+(qz2*qz2)) <= n && qz2<=qz1) {
//gebe Zahlen aus falls das Ergebnis passt
if (((qz1 * qz1) + (qz2 * qz2)) == n) {
printf("Die Zahl %d ist zerlegbar in %d^2 + %d^2.\n", n, qz1, qz2);
}
qz2 ++;
}
qz1 ++;
qz2=0;
}
}
Das funktioniert mit kleinen Zahlen einwandfrei, aber es ist zugegebenermaßen sehr ineffizient und bei grossen Zahlen, wie z.B. 72003446399952, kann man es vergessen, würde ja stundenlang laufen.
Daher meine Frage: Hat jemand einen Vorschlag, wie ich das effizienter gestalten könnte um auch bei sehr grossen Zahlen zu einem Ergebnis zu kommen?