Quadratfreie Zahlen

[Gast]

Hallo!

Ich bin auf der Suche nach einer Methode, um alle quadratfreien Zahlen auszugeben. Habe mir Folgendes überlegt:
Quadratfrei heißt, dass wenn man die Zahl in Faktoren auseinandernimmt (z.B. i) 6 = 2*3; ii) 54 = 2 * 3 * 3 * 3), dass dort keine (Prim)zahl doppelt auftauchen darf. So wäre i) eine quadratfreie Zahl, ii) aber nicht. Soweit richtig, oder?
Somit müsste man doch einfach nur 54 solange durch 2 teilen, bis eine ganze Zahl herauskommt, falls nicht, soll man dann die davorgegangene Zahl nehmen und dann durch 3 teilen, etc. Konkretes Beispiel hieße dann:

20 % 1 == 0 (gerade Zahl)
20 / 2 = 10
10 % 1 == 0 (gerade Zahl)
10 / 2 = 5
5 % 1 == 0 (gerade Zahl)
5 / 2 != 0 (ungerade)
5 % 1 == 0
5 / 3 != 0
....
5 / 5 == 1

Somit wäre 20 = 2 * 2 * 5 * 1 und gleichzeitig eine Quadratzahl, da die 2 zwei Mal vorkommt. Soweit richtig überlegt?

Programmiertechnisch wäre das dann mit einer Schleife zu lösen:

int x = 20;
for (int a = 2; a <= Math.sqrt(x) + 1;) // Damit er nicht größere Zahlen nimmt; 2*5 = 5*2, 5*2 unnötig zu berechnen
{
  if(x % 1 == 0)
  {
    x = x / a;
  }
  if(x % 1 != 0)
  {
    x = x * a; // die Zahl zurückwandeln
    a++; // anscheinend klappte es nicht mit dem a=2 (als Beispiel); dann versuchen wir mit a=3, etc.
  }
}

Ist doch soweit richtig überlegt? Oder kann man sogar noch effizienter lösen?

Grüße, Gast

 

[ttplayer]

1. Das mit der Wurzel ist richtig überlegt.
2. Also x % 1 bringt nichts, du musst x % a machen.

int x = 20;
boolean Quadratzahl = true;
int lastDivisor = 0;
for (int a = 2; a <= Math.sqrt(x) + 1 && Quadratzahl;)
{
  if(x % a == 0)
  {
       if (x != lastDivisor)
       {
           x = x / a;
           lastDivisor = x;    //merkt sich, durch was er schon mal geteilt hat
       }
       else Quadratzahl = false;
  }
  else a++;
}

 

[Gast]

Hallo,
in Anlehnung an deine Fragestellung habe ich auch eine Frage .
Ich soll ein Programm schreiben, das in einem bestimmten Intervall alle Quadratfreien Zahlen ausgibt.

Ich habe mir folgendes überlegt:
[Java]
/****************************** quadratzahlen.java **************************/

import AlgoTools.IO;

/**
* @version 08.11.09
*
* @author Patrick Fox
* @author Christian Viergutz
*/

public class quadratzahlen {

public static void main(String[] argv) {

IO.println("Dieses Programm berechnet alle Quadratfreien Zahlen in einem bestimmten Intervall");
int unten; int oben;
boolean quadratfrei;
int i; int counter;
int letzterTeiler=0;

unten = IO.readInt ("Bitte Untergrenze eingeben: ");
oben = IO.readInt ("Bitte Obergrenze eingeben: ");
while (oben <=unten) {
oben = IO.readInt ("Bitte Obergrenze > als Untergrenze: ");
}

for (i = unten; i <= oben; i++){
counter = i;
quadratfrei = true;
for ( int a = 2 ; quadratfrei == true && a < counter; ){
if (counter % a == 0){

if (counter != letzterTeiler){
counter = counter / a;
letzterTeiler = counter;
}
else quadratfrei = false;

}
else a++;
}
if (quadratfrei = true) {
IO.print( i , 6 );
}
if ( ( i-unten) / 8 == 1) { IO.println();}
}
IO.println();
}
}
[/code]

wenn ich das Progamm ausführe spuckt er mir aber alle Zahlen des intervalls aus. Ich finde den Fehler einfach nicht. Wer kann mir helfen ?

Liebe Grüße

Patrick

 

[Gast]

Guck dir mal Zeile 43 genauer an.

 

[Gast]

Hach... manchmal sieht man den Wald vor lauter Bäumen nicht, was für ein Anfängerfehler . Aber ich bin ja auch einer.
Vielen Dank
Gruß Patrick

 

[Schumi]

Die Technik booleans per "==" auf Gleichheit zu true zu überprüfen sollte man evtl. noch einmal überdenken.