Ermitteln der Anzahl an Lösungen von quatratischen Gleichungen (Sieb von Atkin)

[Lonsdaleit]

Hallo,

ich habe bereits das Sieb des Eratosthenes implementiert.
Nun möchte ich das Sieb des Atkin ausprobieren.

Leider scheitere ich an einer performanten Lösung was die Gleichungen betrifft:

• Falls der Eintrag eine Zahl mit Rest 1, 13, 17, 29, 37, 41, 49, oder 53 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 4x² + y² = n.
• Falls der Eintrag eine Zahl mit Rest 7, 19, 31, oder 43 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² + y² = n.
• Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere ihn für jede mögliche Lösung der Gleichung: 3x² − y² = n, wobei x > y.

Wichtig ist hier nur die Anzahl der Lösungen.
Ich habe bisher einfach "Brute-Force" alle ganzen Zahlen für x und y ausprobiert:

        private static int checkEquation(int n){
		 //n = 4x²+y²
		 int count = 0;
		 for (int x=0; x<Math.sqrt(n);x++){
			 for (int y=0;y<Math.sqrt(n);y++){
				if (n==4*x*x+y*y){
					count++;
				}
			}
		}
		return count;
	}

Leider dauert dies für große Zahlen sehr lang.
Kann ich den zu überprüfenden Zahlenraum weiter einschränken?
Bei der 3ten Gleichung reicht es ja, y nur bis y<x durchlaufen zu lassen.

Es handelt sich bei den überprüften Zahlen n ja um solche mit bestimmten Modulo60 Resten. Dies sollte den Zahlenraum einschränken lassen - nur weiß ich leider nicht wie.

Um einen guten Denkanstoß wäre ich sehr dankbar!!

Gruß,
Lonsdaleit

 

[Konni]

Auf www.pdf-ins-internet.de/primzahlen-test ist erklärt, wie man x und y auf bestimmte Werte beschränken kann.