# Kurze Frage zur Primzahlberechnung



## Javahs (21. Apr 2008)

Juten Tag,
hab da ein Problem. Und zwar komm ich nicht weiter bei folgender Problemstellung :

Primzahlen können wie folgt berechnet werden:
In einer Folge ganzer Zahlen > 1 wird jede einzelne daraufhin untersucht, ob sie durch
(mindestens) eine Zahl, die kleiner ist als sie selbst, ganzzahlig teilbar ist.
 Existiert keine solche Zahl, dann handelt es sich um eine Primzahl, ansonsten nicht.
Überlegen Sie sich anhand eines Nassi-Shneiderman-Struktogramms eine Implementierung
(ohne Arrays!) für diesen Algorithmus und setzen diesen unter Eclipse als Java-Programm um:
 Lesen Sie eine ganze Zahl von der Console ein. Geben Sie dazu eine
Eingabeaufforderung aus und lesen Sie eine Zahl ein.
 Geben Sie alle Primzahlen aus, die kleiner oder gleich dieser eingelesenen Zahl sind.
Anmerkung: Die Primzahlen sollen nicht gespeichert, sondern nur ausgegeben werden.
Weiterhin spielt es keine Rolle, ob die Primzahlen ab- oder aufsteigend abgegeben werden.

Bisher hab ich das:


```
public class primzahlen {


public static void main (String[] args) {


int i = 0;


int j = 0;


int counter = 0;


int eingabe = 97;


int teiler = 0;


int teiler2 = 0;


int counter2 = 0;


teiler = eingabe;



for(i=eingabe; i > 1; i--){


teiler--;


if(eingabe%teiler == 0) { 

counter++; 

}

}

if(counter == 1){

System.

out.println("Primzahl");

}

else{

System.

out.println("Keine Primzahl");

}

}

}
```
[/code]


----------



## SlaterB (21. Apr 2008)

deine Frage ist wirklich kurz: du stellst gar keine


----------



## Javahs (21. Apr 2008)

oh sry^^
Um die Aufgabe zu lösen muss man ja irgendwie 2 Schleifen ineinander packen oder so. Wenn man z.B. eine 7 eingibt soll das Programm die 7 erstmal durch alle Zahlen die kleiner sind als sie (6,5,4,3,2) teilen und gucken ob es einen Rest gibt. Wenn ein Rest rauskommt ist es nicht teilbar und somit eine Primzahl. Jetzt sollen aber auch alle Zahlen kleiner als 7 überprüft werden ob sie eine Primzahl sind. Habs jetzt soweit hinbekommen dass er eine Zahl durch alle kleineren teilt, aber noch nicht die Überprüfung ob die kleineren Zahlen auch primzahlen sind.


----------



## Maeher (21. Apr 2008)

Javahs hat gesagt.:
			
		

> Primzahlen können wie folgt berechnet werden:
> In einer Folge ganzer Zahlen > 1 wird jede einzelne daraufhin untersucht, ob sie durch
> (mindestens) eine Zahl, die kleiner ist als sie selbst, ganzzahlig teilbar ist.


Hab ich Tomaten auf den Augen, oder hat da jemand vergessen Division durch 1 auszuschließen?
Als Methode zum prüfen einer Primzahl kannst du sowas verwenden:

```
static boolean isPrim(int x){
    for(int q=1; q<x; q++) { //Für alle möglichen Teiler
        if(x % q == 0) { //Ohne Rest teilbar
            return false;
        }
    }
    return true; //kein Teiler gefunden-->Primzahl
}
```
(Hoffe ich hab mich nicht vertan, man könnte q<x auch durch q<Math.sqrt(x) ersetzten, das spart Zeit.)
*Edit:* Meine Hoffnung hat sich nicht erfüllt, siehe unten :cry:


----------



## Javahs (21. Apr 2008)

scheiße^^ schon wieder keine Frage gestellt 
Wie krieg ich sozusagen die Schleife um die bereits vorhandene Schleife drumrum, sodass er bei der eingebenen Zahl immer 1 abzieht und dann die ganze Prozedur immer wieder wiederholt?


----------



## Leroy42 (21. Apr 2008)

Mit Maeher's Methode:

(korrigiert:

```
static boolean isPrim(int x){ 
    for(int q=2; q<x; q++) { //Für alle möglichen Teiler 
        if(x % q == 0) { //Ohne Rest teilbar 
            return false; 
        } 
    } 
    return true; //kein Teiler gefunden-->Primzahl 
}
```
)


```
for (int i=2; i<= n; ++i) 
  if (isPrim(i))
    System.out.println(i);
```


----------



## Maeher (21. Apr 2008)

Leroy42 hat gesagt.:
			
		

> Mit Maeher's Methode:
> 
> (korrigiert:


Hast recht, hab nicht aufgepasst.
Aber zu seiner Definition einer Primzahl passt meine Lösung trotzdem besser :lol: 


			
				Javahs hat gesagt.:
			
		

> ob sie durch
> (mindestens) eine Zahl, die kleiner ist als sie selbst, ganzzahlig teilbar ist.


Durch 1 geht immer (oder warum gilt die nicht, Diskriminierung?) ???:L


----------



## Baunty (4. Jun 2008)

hey 

hab sowas auch gerade während meines praktikums gemacht

die variante dauert viiiiel zu lange vorallem bei hohen zahlen ;-)


```
public static void main(String[] args) {
        Prim pr = new Prim();
        pr.berechnePrimzahlenNeu(1000000);  //Musst hier natürlich dein Einlesen noch rein hauen, minimum is hier 8
        
    }

private void berechnePrimzahlenNeu(int bis) {
        
        int i, j, z, anzahlprimzahlen=5;
        long begin = System.currentTimeMillis();
        long dif;
        
        int [] prim = new int[bis];
        
        
        System.out.println("1");
        System.out.println(prim[0] = 1);
        System.out.println(prim[1] = 2);
        System.out.println(prim[2] = 3);
        System.out.println(prim[3] = 5);
        System.out.println(prim[4] = 7);
        
        
        
        for(i = 8; i<bis; i++) {
            
            z=0;

            for(j=0 ; j<anzahlprimzahlen;j++) {
                
                if (i % prim[j] == 0) {
                    z++;
                    if(z>1) {
                        break;
                    }
                }
            }
        
            
            if(z==1) {
                prim[anzahlprimzahlen++] = i;
                System.out.println(i);
            }
            
        }
        
        long ende = System.currentTimeMillis();
        dif = (ende - begin) / 1000;
        this.ausgabe(bis, anzahlprimzahlen, dif);
    }
    
    
    
    private void ausgabe(int grenze, int anzahl, long dif) {
        System.out.println("----------------------------");
        System.out.println("Bis " + grenze + " gibt es " +  anzahl  + " Primzahlen");
        System.out.println("Dauer : " + dif + " Sekunden");
    }
```

geht ca. 100 mal schneller


----------



## Milo (4. Jun 2008)

Hi,


```
/**
  *
  * Beschreibung  Aufgabe 6.1:
  *   Schreiben Sie ein Programm, das eine beliebige natuerliche Zahl ueberprueft,
  *   ob sie eine Primzahl ist oder nicht. Fuer alle Zahlen, die prim sind oder nicht,
  *   sollen die Teiler in einer Zeichenkette ausgegeben werden.
  *
  * @version 1.0 vom 30.05.2006
  * @author Michael Loesler - [url]http://diegeodaeten.de/downloads_datenverarbeitung_java.0.html[/url]
  */

import java.io.*;
public class DV_Aufgabe_6_1 {

  private static int getInputInteger(String question){
    int integervalue = 0;
    System.out.print(question);
    while (true){
      try {
        BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
        integervalue = Integer.parseInt(BR.readLine());
        break;
      }
      catch ( Exception e ){
        System.out.print("Fehler, "+question);
      }
    }
    return integervalue;
  }
  
  private static boolean[] getPrimeNumbers(int n){
    int sqrt_n = (int)Math.ceil(Math.sqrt(n+1));
    boolean A[] = new boolean[n+1];
    for (int i=2; i<=n; i++)
      A[i] = true;
    for (int i=2; i<sqrt_n; i++)
      if (A[i])
        for (int j=i*i; j<=n; j+=i)
          A[j] = false;
    return A;
  }
  
  private static String getDivider(int n){
    String str = "";
    for (int i=1; i<=n; i++)
      if (n%i==0)
        str+=i+", ";
    return str.substring(0,str.length()-2);
  }
  
  public static void main(String[] args) {
    int n = getInputInteger("n: ");
    if (getPrimeNumbers(n)[n])
      System.out.println("Primzahl: "+getDivider(n));
    else
      System.out.println("keine Primzahl: "+getDivider(n));
      
  }
}
```

Gruß Micha


----------

