Zerlegung in Quadratzahlen

Bloodsurfer

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:
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?
 
vielleicht mit einem divide and conquer Algorithmus oder einfach
einen randomisierten Algorithmus entwerfen!
 
.. ich glaube für dieses problem kenn keiner eine lösung auf liniarkomputern in polinomialzeit

ich empfehle dir einen quantencomputer mit wehnigstens 128qbit :D

also random walk ist ein guter lösungsansatz ich würde aber eher matizenmutation verwenden

da hasst du dir aber ein problem ausgesucht über dem du :oldman wirst

.oO( ach du schreck hab ich doch glatt eine mathe vorlesung verpennt )
 
Zuletzt bearbeitet:

Ähnliche Themen

C Code Hilfe!!! gesucht bei Dezimalzahl in Binärzahl for loop

Unix Webserver mit HTML Seite erstellen

Keine grafische Oberfläche (Debian Installation)

Shell Skript beschleunigen

Prozesskommunikation mit PIPES - wie funktioniert das?

Zurück
Oben