Quadratfreie Zahlen ausgeben

[xyZman]

Hi !
Meine Aufgabe ist zwischen zwei Schranken nur die Zahlen auszugeben die quadratfrei sind.
Also deren Primfaktor nur einmal vorkommt.
Das Programm an sich hab ich nun erst einmal so geschrieben, das er mir die Zahlen des Intervalls in Primfaktoren zerlegt. Nur weis ich jetzt nicht wie ich abfrage ob z.b der Teiler 2 mehrmals vorhanden ist. Denn die "20" zb hätte 2*2*5 und darf deshalb nicht angezeigt werden.
Wie bau ich am besten solch eine Abfrage ein ?

import AlgoTools.IO;
public class teiler {

  public static void main(String argv[]) {

  int untergrenze, obergrenze, teiler, i, x;

  untergrenze=IO.readInt("Geben Sie bitte die Untergrenze ein\n");
  obergrenze=IO.readInt("Geben Sie bitte die Obergrenze ein\n");

    while (obergrenze<=untergrenze)
    {
     obergrenze=IO.readInt("Bitte die obere Intervallgrenze eingeben:");
    }

      for(i=untergrenze; i<=obergrenze; i++,IO.println())
      {
      x=i;
      IO.print(x);
        for(teiler=2;teiler<=x; teiler++)
       {
         while(x%teiler==0)

         {

          x=x/teiler;
           IO.print(" " + teiler + "*");
         }
       }
     }

  }
}

Die Ausgabe unten soll noch verschwinden und nur die quadratfreien anzeigen.
mfg
Flo

 

[SlaterB]

erstelle dir ein boolean-Array bis wurzel obergrenze, vor jeder zu testenden Zahl komplett mit false belegt,
für jeden gefundenen Teiler setze das zugehörige Array-Feld auf true, wenn es schon true war dann Quadrat gefunden

bei hohen Interval mit selbst Wurzel im Bereich 1000, Million und höher kann es günstiger sein,
nur die Teiler in einer Liste/ Set zu sammeln und am Ende/ währenddessen nach Doppelten zu schauen,

 

[xyZman]

Du meinst also ich soll ne Hilfsvariable erstellen wo jedesmal geprüft wird ob die bereits geteilte Zahl x/2 != Hilfsvariable ist ?
Mh das werd ich mal machen. Wenn x/2 nämlich = Hilfsvariable ist heißt das ja das bereits einmal durch 2 geteilt wurde und somit keine AUsgabe erfolgen brauch.
Ich werds ma probieren

danke !

Flo

 

[SlaterB]

das stimmt, da du die Teiler in Reihenfolge durchgehst, reicht eine winzige Variable

 

[xyZman]

hab ich jetzt eingebaut. Doch gibt er mir alle Werte aus obwohl ich ihm gesagt habe das nur die wo Quadrahtzahl =false
Wo ist denn der Fehler ?

import AlgoTools.IO;
public class teiler {

  public static void main(String argv[]) {

  int untergrenze, obergrenze, teiler, i, x,letzterteiler;
  Boolean quadratzahl;

  untergrenze=IO.readInt("Geben Sie bitte die Untergrenze ein\n");
  obergrenze=IO.readInt("Geben Sie bitte die Obergrenze ein\n");
 letzterteiler=0;
    while (obergrenze<=untergrenze)
    {
     obergrenze=IO.readInt("Bitte die obere Intervallgrenze eingeben:");
    }

      for(i=untergrenze; i<=obergrenze; i++)//Schleife von 20-30
      {
      x=i;
quadratzahl=true;

        for(teiler=2; quadratzahl == true && teiler<=x; teiler++)
       {
         if(x%teiler==0)
         {
            if(x!=letzterteiler)
{
x=x/teiler;
         }
else quadratzahl =false;
       }
else teiler++;
     }
 if (quadratzahl = false)
{
IO.println("");
}
else
{
IO.println(i);
}
}
}
}

 

[SlaterB]

if (quadratzahl = false)

if (quadratzahl == false)

 

[Michael...]

Wo ist denn der Fehler ?

Die ganze innere Schleife ist - wie man bei uns hier so sagt - Schmarrn ;-)

Fürn Anfang könntest Du so vorgehen:
- teile eine Zahl solange durch teiler bis der Rest !=0 ist
- zähle dabei wie oft die Zahl geteilt wurde
- wenn die Zahl öfter als einmal geteilt wurde ==> quadratzahl = false;
- ansonsten teiler++

Im zweiten Schritt könnte man das optimieren.

Hinweis: In Java wird mit == auf Gleichheit geprüft:

if (quadratzahl == false)

oder

if (!quadratzahl)

statt:

if (quadratzahl = false)

 

[Andi_CH]

if (quadratzahl = false)

if (quadratzahl == false)

Da krieg ich jedes mal Schübe

if (!quadratzahl) {
   blabla;
{

ist die einzige vernünftige Abfrage eines booleans

Stell dir mal vor

boolean error = false;
..... code .....
if (!(!error != false))
    system.out.println("so ein Käse!");

Logisch ist das eine Karikatur aber nur schon if (Error != true) - igitt .....
Ein boolean muss - nö darf! - NIE mit true oder false verglichen werden. Ein einfaches if (error) oder allenfalls if (!error) reicht vollständig. Der Kompiler hat sicher keine Mühe mit dem Statement oben, aber der Kollege der später einmal den Code warten muss, wird das anders sehen.
(Wie war das mit dem Wettbewerb bei dem die unleserlichste Zeile C Code gesucht wurde?)

Das mit dem = als Zuweisungsoperator haben die Javaentwickler leider von C übernommen und somit sind die Fehler vorprogrammiert.
Mir gefällt das := von Pascal, Modula, Ada und Konsorten viel besser

 

[Landei]

Für kleine Zahlen reicht...

public static boolean squareFree(int n) {
    for(int i = 3, k = 4; k <= n; i += 2, k += i) {
        if(n % k == 0) return false;
    }
    return true;
}