Primfaktorzerlegung

[Uzi88]

hallo das ist meine aufgabe

http://puu.sh/5Iu6r.png

import java.util.Scanner;


public class Aufgabe36 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner scan = new Scanner(System.in);
		
		System.out.println("n? ");
		
		double n = scan.nextDouble();
		boolean m = false; 
		
		for (int i = 2; i*i <= n && !m; i++)
		{
			if( n % i == 0)
			{
				m = true;
			}
		}
		if(!m  && n > 1 )
		{
			System.out.println("ist prim");
		}

	}
}

ich bin schon so weit dass das programm mit anzeigt ob es ein prim ist oder nicht nur wie geht es weiter?
ich stell mir das so vor das wenn es keine prim ist teilt es ja durch 2 und bei jeder wiederholung +1 oder?

 

[Gucky]

Hä? Ich verstehe überhaupt nicht, was du meinst, mit "ich stell mir das so vor das wenn es keine prim ist teilt es ja durch 2 und bei jeder wiederholung +1[...]"

Nicht jede Nichtprimzahl muss durch zwei teilbar sein. Auch nicht durch drei. Vielleicht ist sie durch irgendwas riesiges teilbar.


Wenn die Zahl keine Primzahl ist, ist sie vielleicht ein Vielfaches von 2. Dann checkst du, wie oft die 2 da reinpasst. Diese Zahl zerlegst du dann wieder, bis es nicht weiter geht. Das ist aber nur eine spontane Idee.

Für Verfahren um die Primfaktoren zu berechnen guck mal hier.

 

[njans]

Also das, was du da berechnest, ist kein Primfaktor.
Du berechnest nur einen Teiler, Primfaktoren sind aber, wie der Name sagt, Primzahlen.
Du musst dann nur gucken, ob es eine Kombination von Primzahlen bis wurzel(n) (korrigiert mich hier, wenn ich mich falsch erinnere) gibt, die dann als Produkt deine Zahl ergeben.

 

[Uzi88]

ja ich habs jetzt ^^ falls jemand bessere idee hat ich bin offen :toll:

import java.util.Scanner;



public class Aufgabe36 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		

			Scanner scan = new Scanner(System.in);
			System.out.println("Zahl eingeben: ");
			int n = scan.nextInt();
			int a = n;
			int i = 2; 
			String prfa = "";

			for (i = 2; i <= n; ) {
				if (n % i == 0) {
					
					if (n%i == 0 && a != n) {
						prfa += " * ";
					} 

				
					
					
					prfa += i;
					n = n / i;
					

				} else {
					i++;
				}

			}
			System.out.println("lässt sich zerlegen in: " + prfa);
		}
	}

 

[Klösp]

Hallo
hab es parallel auch mal ausprobiert.
Vom Prinzip hab ich es fast genauso gelöst, nur mir Rekursion.
Sollte von daher kaum ein Unterschied machen.


Hier mal zum Vergleich:

import java.util.ArrayList;

public class Primfaktorzerlegung {


    public static void main(String[] args) {
        for (long i : primfaktorzerlegung(9223372036854775807L)) {
            System.out.println(i);
        }
    }

    public static ArrayList<Long> primfaktorzerlegung(long i) {
        ArrayList<Long> faktoren = new ArrayList<>();

        findeFaktor(i, faktoren);

        return faktoren;
    }

    private static void findeFaktor(long i, ArrayList<Long> faktoren) {
        long j = 2;
        while (((i % j) != 0) && (j != i) && (i > j)) {
            j++;
        }
        if (i > j) {
            faktoren.add(j);
        } else {
            faktoren.add(i);
        }
        if (i != j && i > j) {
            findeFaktor((i / j), faktoren);
        }
    }

}

Wobei ich die Faktoren jetzt in einer Liste speichere und nich direkt als String ausgebe.

 

[Uzi88]

ja das sieht gut aus, nur verstehe ich da einiges nicht...
z.b. in zeile 7 diese lange zahl in der klammer was ist das? und in 26 & 28 was ist diese add?

 

[Klösp]

1:
Das ist nur die notation für long, also Ganzzahlen mit 64bit (int hat 32bit) codierung.

2. Das add für den gefundenen Faktor der Liste hinzu, in der ich alle Faktoren speichere.

Ich habe gerade das gefühl, dass ich damit vermutlich etwas vorgegriffen habe.
Falls du von so etwas wie ArrayList noch nicht wirklich was gehört hast, dann vergesse die Lösung von mir einfach erstmal.
Dazu wirst du dann später noch kommen.

 

[Uzi88]

ne array und so hatten wir schon nurr dieses add. ist mir fremd und diese zahl.. hast du die selber eingegeben oder enteht die von selbst und vor allem wie gibt man sie ein

 

[Gucky]

Die Zahl ist nur irgendeine, weil Klösp keine Lust hatte noch extra das Einlesen zu Programmieren.

 

[Uzi88]

verstehe ich nicht ^^

 

[Gucky]

Wie du schon richtig bemerkt hast, müsste die Zahl irgendwo herkommen. Klösp hatte aber keine Lust das noch zu programmieren, deshalb hat er diese Zahl einfach in den Code geschrieben.

 

[Klösp]

Die Zahl ist die ich gewählt hab ist die höchste positive Zahl die man mit long speicher kann.
Mit der lässt sich das zufälligerweise auch relativ schnell lösen.^^

Eine ArrayList ist nicht das selbe wie ein Array. Die ArrayList hat z.B keine vorgegebenen Länge.
Aber wieso das so ist, wirst du vermutlich zu einem späterem Zeitpunkt noch erfahren.
Deshalb einfach erstmal ignorieren.

€dit:
Lässt sich das für 922337234254775807 mit diesem trivialen Ansatz nur schleche lösen, oder ist bei mir noch ein Fehler drin?

 

[Uzi88]

ok ^^
trotzdem danke an alle für die hilfe