Prüfen ob Zahl quadratfrei ?

[Guest]

Hallo,

ich suche einen schnelleren Algorithmus als den hier, um zu prüfen ob eine Zahl quadratfrei ist:

	public static boolean isSquareFree(double testSubject){
		double answer;
		for(int i = 1; i < testSubject; i++){
			answer = Math.sqrt(testSubject / (double)i);
			if(answer < 1){
				return false;
			}
			if(answer % 1.0 == 0){
				return false;
			}
		}
		return true;
	}

Kann mir da jemand weiterhelfen?

 

[SlaterB]

ständig Wurzel zu berechnen ist schlecht,
aber (zunächst) einmal Wurzel berechnen ist schon sinnvoll:
du musst nämlich maximal alle Zahlen bis zur Wurzel von testSubject testen,

ist testSubject beispielweise 6500, dann musst du nicht 6500 verschiedene Teiler testen sondern nur 81,
da 81 * 81 > 6500 ist, sind höhere Zahlen uninteressant

überhaupt bieten sich viele Verfahren aus Primzahltests und Primfaktorzerlegung an,
suche danach bei google oder gleich hier:
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes

Vorgehensweise: Primfaktoren finden, aus der Zahl entfernen so oft sie vorkommen,
wenn eine Primzahl doppelt drin, dann schon fertig, ansonsten mit der kleineren Zahl weitermachen

Beispiel: 9295
testen ob teilbar durch 2, durch 3, durch 4 (evtl. alle geraden Teiler auslassen da schon durch 2 getestet)
durch 5 -> einmal drin, Rest 1859, weitermachen,
durch 6 (evtl. alle Vielfachen von 3 auch weglassen da schon durch 3 geprüft, das ist das Sieb von Eratosthenes)
durch 7,
durch 11, -> 11 ist Teiler aber auch nur einmal, Rest 169
durch 13 -> 2x Teiler, keine Quadratzahl


wenn man die Zahl verkleinert, kann man evtl. auch die Obergrenze neu festlegen, die Wurzel von 9295 war 96,
also würde man initial alle Zahlen von 1 bis 96 testen,
die Wurzel von 169 ist aber nur noch 13, also auch wenn es nicht zufällig gerade ein Teiler wäre,
hätte man nun recht bald nach der 13 aufhören können statt noch bis 96 durchzutesten

 

[Frankyboy]

Eine Zahl n ist quadratfrei, wenn der zugeh. Restklassenring reduziert ist, also kein nilpotentes Element besitzt

http://de.wikipedia.org/wiki/Quadratfrei

public class Util {
	public static boolean istQuadratfrei(int basis){
		int i = 0;
		do {
			i++;
		}while (!istnilpotent(i, basis)); 
		return (i == basis);
	}
	public static boolean istnilpotent(int n, int basis) {
		int produkt = n;
		ArrayList<Integer> produkte = new ArrayList<Integer>();
		do {
			produkte.add(produkt);
			produkt = (produkt*n)%basis;
		}while(!produkte.contains(produkt));
		return (produkt == 0);
	}
	public static void main (String[] args) {
		for (int i=1; i<100; i++)
		System.out.println(i+" "+istQuadratfrei(i));
	}
}

 

[0x7F800000]

Eine Zahl n ist quadratfrei, wenn der zugeh. Restklassenring reduziert ist, also kein nilpotentes Element besitzt

Naja, die Aussage kann man wohl nur als Garantie in die andere Richtung nehmen, aber nicht als Kriterium für Quadratefreiheit :roll:
der Aufwand von der von dir vorgeschlagenen Methode ist extrem gigantisch, ich würde fast behaupten, dass man da mit bruteforce-faktorisierung besser dran wäre ???:L

 

[SlaterB]

die Aussage im Wiki ist etwas anders
"Eine Zahl n ist genau dann quadratfrei, wenn der Restklassenring reduziert ist, das heißt wenn außer der Null kein nilpotentes Element enthalten ist."
könnte also schon passen, wenn ich das 'genau dann' richtig erinnere

 

[0x7F800000]

könnte also schon passen, wenn ich das 'genau dann' richtig erinnere

ich hab kein problem mit dem "genau dann", sondern mit dem abartig hohen aufwand. :roll:

 

[visualG]

alle primzahlen >3 haben die eigenschaft p = 6n +- 1. Das reduziert schonmal die zu testen zahlen. Du kannst mit ner schleife n hochzählen, die zahl quadrieren und gucken ob sie bei der Division rest 0 lässt. wenn ja, dann hast du ne quadratzahl, wenn nein weitermachen bis 6n+-1 größer als X ist

public boolean quadratfrei(int zahl)
{
int temp;
if (zahl % 2 == 0 || zahl % 3 == 0) return false;

for(int n = 1; n <= (zahl +1) / 6; n++)
{
temp = (6*n+1);
temp *= temp;
if (zahl % temp == 0) return false;
if (zahl % temp -24*n == 0) return false;
}
return true;

Kann man auch für Primzahlen größer 3 machen, zB n*30+-1,7,11,13

EDIT: Hab code nochmal bischen korrigiert. Also für Integer.MAX_VALUE braucht mein programm 3sec. reicht das an performance?

 

[Ark]

Lookup-Tables oder Bäume mit quadratfreien Zahlen könnten ebenfalls zur Geschwindigkeitssteigerung betragen - auf Kosten von Speicher, versteht sich. Dazu wäre jetzt interessant, aus welchem Intervall die zu untersuchenden Zahlen überhaupt kommen; als Kompromiss reicht es vielleicht sogar, nur sehr häufig auftretende Kandidaten aufzunehmen.

Ark

 

[visualG]

Ich frag mich warum ihr alle so extrem auf zeit optimieren wollt. eine 32bit zahl hat als größten quadratteiler eine 16bit zahl und Alle 6n+-1 zahlen bis 0xFFFF zu testen ist rechenaufwand, was max. 1 sec dauert, wohl gemerkt wenn die Zahl 32bit hat. Meistens sind es ja 10-20 bit weniger. Wozu hat mat GHZ CPUs (10^9. Opperationen/s , 2^16 ~ 10^4,8 zum vergleich )

 

[0x7F800000]

eine 32bit zahl...

...ist ein gewöhnlicher Integer, und damit für jegliche zahlentheoretische Untersuchungen/Anwendungen völlig uninteressant/unbrauchbar. Da spielt man schon wesentlich lieber mit paar-hundert-stelligen Zahlen herum, das kann kein Mensch und kein Tier und kein Superrechner per Bruteforce mit Probedivision durchprobieren.

 

[Guest]

alle primzahlen >3 haben die eigenschaft p = 6n +- 1. Das reduziert schonmal die zu testen zahlen. Du kannst mit ner schleife n hochzählen, die zahl quadrieren und gucken ob sie bei der Division rest 0 lässt. wenn ja, dann hast du ne quadratzahl, wenn nein weitermachen bis 6n+-1 größer als X ist

public boolean quadratfrei(int zahl)
{
int temp;
if (zahl % 2 == 0 || zahl % 3 == 0) return false;

for(int n = 1; n <= (zahl +1) / 6; n++)
{
temp = (6*n+1);
temp *= temp;
if (zahl % temp == 0) return false;
if (zahl % temp -24*n == 0) return false;
}
return true;

Kann man auch für Primzahlen größer 3 machen, zB n*30+-1,7,11,13

EDIT: Hab code nochmal bischen korrigiert. Also für Integer.MAX_VALUE braucht mein programm 3sec. reicht das an performance?

Leider ist der Code nicht korrekt.
Denn 6 ist beispielsweise quadratfrei, wird aber von obiger Methode als nicht quadratfrei angegeben.

 

[visualG]

Ja, stimmt. Ich muss ja auch auf 4 und 9 testen und nich tauf 2 und 3. Außerdem reicht es bis zur Wurzel aus n zu rechnen

public boolean quadratfrei(int zahl)
{
int temp;
if (zahl % 4 == 0 || zahl % 9 == 0) return false;

for(int n = 1; n <= (int) (Math.Sqrt(zahl) +1) / 6; n++)
{
temp = (6*n+1);
temp *= temp;
if (zahl % temp == 0) return false;
if (zahl % temp -24*n == 0) return false;
}
return true;

 

[SlaterB]

bitte bitte nicht optimieren, indem nur bis zur wurzel von zahl geprüft wird und dann diese Wurzel in der for-Schleife in jeder Runde neu ausrechnen(!)

egal ob der Compiler das vielleicht wegoptimiert,
vorher in eine Variable schreiben und die Sache ist erledigt

 

[0x7F800000]

am besten gar keine wurzel ziehen, sondern durch >> etwas gröber als durch wurzel abschätzen, diese wurzelzieherei kostet mehr als die paar zahlen zuviel, die man sonst prüft... könnte zumindest so sein...

 

[Gast]

Was meinst du mit >> die wurzel abschätzen?
Du meinst doch Bitverschiebung oder? Wie kann man damit die ungefähre Wurzel abschätzen?

 

[SlaterB]

bei einer Zahl mit 20 Bit kann wohl maximal 2^20 vorliegen, davon die Wurzel ist 2^10

da braucht man gar nicht unbedingt verschieden, wenn man erstmal das höchste Bit bestimmt hat (doch wiederum durch Verschieben?),
kann man auch aus einem Array die passende Wurzel entnehmen

die Bandbreite zwischen 2^9 und 2^10 ist allerdings gleich nochmal 2^9, also mit Pech eine Verdopplung der Arbeit,
ob das mit 'die paar zahlen zuviel' noch einhergeht?,
nur um die Wurzel einmalig nicht auszurechnen?
vielleicht gehts aber noch genauer