# Programm zu Ermittlung von Primzahlen



## super_junior (23. Mrz 2011)

Hallo!
Ich soll ein Programm schreiben,dass prüft ob bestimmte Zahlen Primzahlen sind,dabei soll die Methode einen boolean zurückgeben
Ich bin leider noch ein Anfänger und weiß leider gar nicht was ich da falsch gemacht habe.Das Programm funktioniert auch leider nicht.


public class Primzahlen {

   public static boolean istPrim(int n){

    boolean primZahl=true;

    while(n>0){

    if(n%2==0){
     primzahl=false;

    }
    else if(n%3==0){
     primzahl=false;

    }

    }return primZahl; 



    }





}
  public static void main(String[] argv) {


  for(int number=2;number<=20;i++){
  IO.println(istPrim(number));

  }

}


----------



## antrox (23. Mrz 2011)

```
public class Primzahlen {

public static boolean istPrim(int n){

boolean primZahl=true;

while(n>0){

if(n%2==0){
primzahl=false;

}
else if(n%3==0){
primzahl=false;

}

}return primZahl; 



}





}
public static void main(String[] argv) {


for(int number=2;number<=20;i++){
IO.println(istPrim(number));

}

}
```


----------



## antrox (23. Mrz 2011)

ich hab es jetzt nicht getestet, aber du hast in der for schleife "number" als zaehlervariable und dann machst du "i++"`?

da muss "number++" hin. kann sein, dass es daran liegt.

da du noch anfaenger bist und "learning by doing" am besten ist in java solltest du das selber weiter ausprobieren 

gruß


----------



## W9ND3R (23. Mrz 2011)

Du hast auch in deiner Methode istPrim() die Variable einmal "primZahl" und einmal "primzahl" genannt!
Die sollte eigentlich gleich heißen ;-)


----------



## Final_Striker (23. Mrz 2011)

Du hast eine Endlosschleife, weil du in deiner while-Schleife das n nicht veränderst.


----------



## W9ND3R (23. Mrz 2011)

Hab jetzt kurz was versucht mit deinem Ansatz.
Die 2 und die 3 werden natürlich nicht als Primzahlen angezeigt, aufgrund des Verfahrens.

```
public class Primzahlen {

	public static boolean istPrim(int n) {
		boolean primzahl = true;
		if ((n % 2) == 0 || (n % 3) == 0) {
			primzahl = false;
		}
		return primzahl;
	}

	public static void main(String[] argv) {
		for (int number = 2; number < 20; number++) {
			System.out.println("Die Zahl " + number + " ist eine Primzahl? " + istPrim(number));
		}
	}
}
```
Vielleicht hilfts als Denkanstoß ...


----------



## r.w. (9. Apr 2011)

W9ND3R hat gesagt.:


> Hab jetzt kurz was versucht mit deinem Ansatz.
> Die 2 und die 3 werden natürlich nicht als Primzahlen angezeigt, aufgrund des Verfahrens.
> 
> ```
> ...



Wobei diese Funktion auch nur bis 24 korrekte Werte zurückliefert
und schon mit 25 die erste Zahl fälschlicher Weise als Primzahl ausgeben würde. ;-)

VG ROlf


----------



## Marco13 (9. Apr 2011)

Das nennt sich "vollständige Induktion": 
*Verankerung:* n=1 ist eine Primzahl
*Induktionsschritt:* n+1=2 ist eine Primzahl
*Induktionssschluss:* Alle Zahlen sind Primzahlen
:joke:


----------



## r.w. (9. Apr 2011)

Marco13 hat gesagt.:


> Das nennt sich "vollständige Induktion":
> *Verankerung:* n=1 ist eine Primzahl
> *Induktionsschritt:* n+1=2 ist eine Primzahl
> *Induktionssschluss:* Alle Zahlen sind Primzahlen
> :joke:



Aha,
man lernt doch immer noch wieder etwas Neues dazu...


----------



## Landei (9. Apr 2011)

Erbarmt sich niemand? Na gut...


```
public static boolean istPrim(int n){
   boolean primZahl=true;  //... solange wir keinen Teiler gefunden haben
   int moeglicherTeiler = 2;  
   while(moeglicherTeiler  < n){ //Teiler muss kleiner sein als Zahl selbst
      if(n % moeglicherTeiler==0) { //Teiler gefunden -> keine Primzahl
          primZahl=false;
      }
      moglicherTeiler = moeglicherTeiler + 1;  //Teiler hochzählen
   }
   return primZahl;
}
```

Das sollte funktionieren, lässt sich aber in vieler Hinsicht verbessern:
- eine bessere obere Schranke ist sqrt(n)
- beim ersten gefundenen Teiler kann die Schleife bereits verlassen werden
- man braucht Teilbarkeit durch gerade Zahlen außer 2 nicht zu testen


----------



## kirax (9. Apr 2011)

Mitunter am effektivsten ist es wahrscheinlich, wenn du eine Liste erstellst, wo alle bereits gefundenen Primzahlen reinkommen.
Für jedes n versuchst du dann, dieses restlos durch jede der Zahlen in der Liste (in aufsteigender Reihenfolge) zu teilen.
Findest du keinen Teiler, ist n eine Primzahl (und kommt dann auch in die Liste).

Dazu noch als obere Schranke sqrt(n) und du bist schon relativ fix unterwegs


----------



## mathee (9. Apr 2011)

Landei hat gesagt.:


> Das sollte funktionieren, lässt sich aber in vieler Hinsicht verbessern:
> - eine bessere obere Schranke ist sqrt(n)
> - beim ersten gefundenen Teiler kann die Schleife bereits verlassen werden
> - man braucht Teilbarkeit durch gerade Zahlen außer 2 nicht zu testen



ohne jetzt zu sehr von java abzuschweifen, wieso braucht man mit anderen Zahlen, die nicht unter Punkt 1 und 3 fallen, nicht mehr zu testen?

Und das andere wäre sieb des eratosthenes


----------



## Landei (9. Apr 2011)

Punkt 1: Angenommen der kleinste echte Teiler a einer zusammengesetzten Zahl n wäre größer als sqrt(n). Sei b = n / a. Dann ist b ebenfalls ein echter Teiler von n, und nach Voraussetzung ist b mindestens so groß wie a, also ebenfalls größer als sqrt(n). Aus a > sqrt(n) und b > sqrt(n) folgt a*b > n, Widerspruch! 
Also muss von den Teilern einer zusammengesetzten Zahl mindestens einer kleiner als deren Wurzel sein.
Punkt 3: Wenn eine Zahl n *nicht *durch eine Zahl k teilbar ist, ist sie auch nicht durch Vielfache von k teilbar. Die geraden Zahlen sind Vielfache von 2.


----------



## mathee (9. Apr 2011)

Landei hat gesagt.:


> Punkt 1: Angenommen der kleinste echte Teiler a einer zusammengesetzten Zahl n wäre größer als sqrt(n). Sei b = n / a. Dann ist b ebenfalls ein echter Teiler von n, und nach Voraussetzung ist b mindestens so groß wie a, also ebenfalls größer als sqrt(n). Aus a > sqrt(n) und b > sqrt(n) folgt a*b > n, Widerspruch!
> Also muss von den Teilern einer zusammengesetzten Zahl mindestens einer kleiner als deren Wurzel sein.



und, frage 1: ist jede nicht-primzahl eine zusammengesetzte zahl? 2: warum folgt aus b=n/a das b ebenfalls teiler von n ist? den rest versteh ich ja...


----------



## Illuvatar (9. Apr 2011)

1: Ja. Zumindest in den ganzen Zahlen (bzw in Hauptidealringen), aber ich denke darum geht es hier 
2: Wenn b=n/a ist, dann ist n = a*b, also b ein Teiler von n...


----------

