# primzahlen im array



## ringelking96 (26. Okt 2016)

moin, ich möchte gerne ein programm schreiben, welches mir die ersten 10 primzahlen in einem array ausgibt und brauche da etwas hilfe. also ich habe bis jetzt es geschafft, mithilfe zweier for-schleifen zu ermitteln, welche zahlen nur 2 teiler haben, jedoch kriege ich sie nicht in meinenen array gespeichert, sondern gebe sie nur einfach so ohne den array aus. ebenfalls musste ich die maximale zahl auf 30 setzen, um nicht über 10 zahlen auszugeben, da wusste ich auch wie ich es mache, dass er nur 10 nimmt. mein coe is bis jetzt so:

```
public class Primzahlen {

    public static void main(String[] args) {

        int[] Primzahlen;
      
        Primzahlen = new int[10];
        for(int i=1; i<=30; i++)
        {
            int teilbar = 0;
            for(int j=1; j<=i; j++)
            {
                if (i % j == 0)
                {
                    teilbar++;
                }
              
            }
          
            if(teilbar == 2)
            {
                System.out.print(i + " ");
            }
          
          
        }
    }

}
```
hätte da gerne tipps wie ich es mit array schaffe wie gesagt.
danke


----------



## JStein52 (26. Okt 2016)

An der Stelle wo du die Primzahl gefunden hast und sie jetzt nur ausgibst schreibst du sie einfach in dein Array Primzahlen. Damit du weisst an welche Stelle du sie dort schreiben musst führst du einen eigenen Zähler mit den du nach jeder Primzahl die du kopiert hast um eins erhöht, so dass dass dieser Zähler immer auf die nächste freie Stelle in "Primzahlen" zeigt.


----------



## JStein52 (26. Okt 2016)

etwa so:


```
if(teilbar == 2) {
   System.out.print(i + " ");
   Primzahlen[nextPrim++] = i;
}
```


----------



## JStein52 (26. Okt 2016)

Und das mit der Begrenzung für i auf 30 kannst du auch noch wegkriegen wenn du halt einfach abfragst ob du schon soviele Primzahlen gefunden hast wie in das Array passen, z.B. indem du die Abbruchbedingung deiner for (int i.... ) - Schleife so formulierst dass sie endet wenn nextPrim grösser gleich der Länge des Arrays wird.


----------



## ringelking96 (26. Okt 2016)

ok danke mein code sieht jz so aus:

```
public class Primzahlen {

    public static void main(String[] args) {

        int[] Primzahlen;
        int nextPrim =1;
        Primzahlen = new int[10];
        for(int i=1; nextPrim<=Primzahlen.length; i++)
        {
            int teilbar = 0;
            for(int j=1; j<=i; j++)
            {
                if (i % j == 0)
                {
                    teilbar++;
                }
              
            }
          
            if(teilbar == 2)
            {
              
                System.out.println(i + " ");
                    Primzahlen[nextPrim++] = i;
              
              
            }
          
          
        }
    }

}
```

dann kommt ein error wegen "exception: 10 in Primzahlen" klappt also noch nicht


----------



## JStein52 (26. Okt 2016)

etwa so:


```
Primzahlen = new int[10];
int nextPrim = 0;
for(int i=1; nextPrim<Primzahlen.length; i++)  {
.......
```


----------



## JStein52 (26. Okt 2016)

Bei deinem Code bleibt Primzahlen[0] leer. Arrays fangen in Java mit dem Index 0 an. Und wenn du versuchst in Primzahlen[10] zu schreiben kriegst du eine Exception


----------



## JStein52 (26. Okt 2016)

ringelking96 hat gesagt.:


> dann kommt ein error wegen "exception: 10 in Primzahlen" klappt also noch nicht


Genau. du musst nextPrim mit 0 initialisieren und bei der schleife auf < length abfragen


----------



## ringelking96 (26. Okt 2016)

wenn ich nextPrim auf 0 setze ist es das gleiche, und wenn ich Primzahlen[nextPrim++] = i; auf Primzahlen[++nextPrim] = i; ändere kommt  die fehlermeldung immernoch


----------



## ringelking96 (26. Okt 2016)

ah habe es, vielen dank!!


----------



## Xyz1 (26. Okt 2016)

Hier mal eins für die ersten 25:

```
int[] array = IntStream.range(1, 100).map(o -> o % 2 == 0 ? 0 : o).toArray();
        for (int i = 2; i < array.length; i++) {
            if (array[i] != 0) {
                for (int j = i + 2; j < array.length; j += 2) {
                    if (array[j] % array[i] == 0) {
                        array[j] = 0;
                    }
                }
            }
        }
        Arrays.stream(array).filter(o -> o != 0).mapToObj(o -> o + ", ").forEach(System.out::print);
```


```
1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
```

Sollte eigentlich flux gehen, wenn ich mich nicht irgendwo vertan hab. 

Anmerkung: Jepp, die innere Schleife ist falsch


----------



## JStein52 (26. Okt 2016)

DerWissende hat gesagt.:


> Sollte eigentlich flux gehen, wenn ich mich nicht irgendwo vertan hab.
> 
> Anmerkung: Jepp, die innere Schleife ist falsch


Das ist für einen Anfänger einfach nur Käse .....


----------



## Xyz1 (26. Okt 2016)

Hier nochmal richtig:

```
public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        int[] array = sieb(10000000);
        long t2 = System.currentTimeMillis();
        System.out.println(Arrays.toString(array));
        System.out.println(t2 - t1);
    }

    private static int[] sieb(int end) {
        int[] array = IntStream.range(0, end).map(o -> o % 2 == 0 ? 0 : o).toArray();
        for (int i = 3; i < array.length; i += 2) {
            if (array[i] != 0) {
                for (int j = array[i] * 2; j < array.length; j += array[i]) {
                    array[j] = 0;
                }
            }
        }
        return Arrays.stream(array).filter(o -> o != 0).toArray();
    }
```

könntet ja mal messen.

Wieso denn Käse? Du bist gemein. 

Anmerkung: Immernoch zu kompliziert, schreibe (spart 10 %):

```
for (int i = 3; i < array.length; i += 2) {
            if (array[i] != 0) {
                for (int j = i * 2; j < array.length; j += i) {
                    array[j] = 0;
                }
            }
        }
```

Man man man, heute nur Mist.


----------



## JStein52 (26. Okt 2016)

Ich will dem TE und dir ja nicht zu nahe treten, aber Käse deshalb: wenn du Probleme hast zu wissen wie die Indizes in einem int-Array sind und du nicht so genau weisst wie du die Schleifenbedingung zu formulieren ist dann stehst du halt noch ziemlich am Anfang. Und dann versteht man deinen Code da oben überhaupt nicht. Dann sollte man ihn zuerst mal seinen eigenen Code verstehen lassen und ihm nicht Lambda's an den Kopf knallen. Das mit dem Käse war keine Wertung deines Codes. Der ist sicher ganz cool.


----------



## Xyz1 (26. Okt 2016)

JStein52 hat gesagt.:


> und du nicht so genau weisst wie du die Schleifenbedingung zu formulieren ist


Was soll das denn heißen? Ich weiß alles, aber habe lediglich etwas vorschnell agiert. Kein Grund, sich aufzuregen.

Edit: Lambdas deswegen, weil ihr die auch hin und wieder schreibt.


----------



## JStein52 (26. Okt 2016)

DerWissende hat gesagt.:


> Was soll das denn heißen? Ich weiß alles


Doch nicht du. Der TE !!!

Edit: nicht gleich aufregen


----------



## Xyz1 (26. Okt 2016)

Teste mal, ob es mit Lambdas gegenüber normalen Arrays schneller ist:

```
public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        int[] array = sieb(100000000);
        long t2 = System.currentTimeMillis();
        System.out.println(array[array.length - 1]);
        System.out.println(t2 - t1);
    }

    private static int[] sieb(int end) {
        int[] array = IntStream.range(0, end).map(o -> o % 2 == 0 ? 0 : o).toArray();
        for (int i = 3; i < array.length; i += 2) {
            if (array[i] != 0) {
                for (int j = i * 2; j < array.length; j += i) {
                    array[j] = 0;
                }
            }
        }
        return Arrays.stream(array).filter(o -> o != 0).toArray();
    }
```

Endlich mal ist der Speicher das Problem dabei.


----------



## JStein52 (26. Okt 2016)

Ein hand made Erathostenes-Sieb ist doppelt so schnell wie deines mit diesen Teufels-Lambdas. Gerade getestet


----------



## Xyz1 (26. Okt 2016)

Ich glaub, mit Lambdas ist das alles Verars...  Hab mir schon fast so etwas gedacht.

Jedenfalls, es liefert die ersten N Primzahlen, wobei man vorher noch nicht sagen kann, wie viele... da müsste man auch anders ran.


----------



## neoexpert (30. Okt 2016)

Hab mal aus spass folgende Primzahl Berechnung geschrieben:

```
import java.util.*;

public class Main
{

    public static void main(String[] args)
    {
        ArrayList<Integer> p=new ArrayList<Integer>();
        int i=1;
      
        while (true)
        {
            i++;
            boolean prim=true;
            int sqrti=(int)Math.sqrt(i)+1;
            for (Integer n:p)
            {
                if(n>sqrti)
                    break;
                if (i % n == 0)
                {
                    prim = false;
                    break;
                }
            }
            if (prim)
            {
                p.add(i);
                System.out.println(i);
              
            }

        }
    }
}
```


----------



## Xyz1 (30. Okt 2016)

Geht auch, wäre der umgekehrte Ansatz, Math.sqrt() ist ein guter Punkt 

Bearbeitung: Nochmal etwas in geändert, sollte man so nicht machen, nur für Profis:

```
private static int[] sieb(int end) {
        ArrayList<Integer> p = new ArrayList<>();
        a:
        for (int i = 3; i < end; i += 2) {
            int sqrt = (int) Math.sqrt(i) + 1;
            for (Integer integer : p) {
                if (integer > sqrt) {
                    break;
                }
                if (i % integer == 0) {
                    continue a;
                }
            }
            p.add(i);
        }
        return p.stream().mapToInt(e -> e).toArray();
    }
```


----------



## neoexpert (30. Okt 2016)

Ich möchte demnächst RSA Algorithmus in Java machen. Da braucht man Riesiege Primzahlen. Wie bekommt man Primzahlen die mehrere hundert stellen haben?


----------



## Xyz1 (30. Okt 2016)

neoexpert hat gesagt.:


> Ich möchte demnächst RSA Algorithmus in Java machen. Da braucht man Riesiege Primzahlen. Wie bekommt man Primzahlen die mehrere hundert stellen haben?


Ach bitte, soll das jetzt wieder eine Endlosdiskussion werden?


----------



## neoexpert (30. Okt 2016)

Wir haben (ich zumindest) durch diese sehr viel gelernt. Ich mag diesen Forum deshalb sehr.


----------



## JStein52 (30. Okt 2016)

BigDecimal !


----------



## Xyz1 (30. Okt 2016)

Mist, kann das nicht mehr bearbeiten, sieb(int end) ist eigentlich nicht für Öffentlichkeit gedacht. 
Und zur anderen Frage, meine mathematischen Skillz sind für die Beantwortung dieser Frage nicht ausreichend.


----------



## neoexpert (30. Okt 2016)

```
import java.util.*;
import java.math.*;

public class Main
{

    public static void main(String[] args)
    {
        ArrayList<BigDecimal> p=new ArrayList<BigDecimal>();
        BigDecimal i=new BigDecimal(1);
        //Scanner sn=new Scanner(System.in);
        while (true)
        {
            i=i.add(new BigDecimal(1));
            boolean prim=true;
            //int sqrti=(int)Math.sqrt(i)+1;
            for (BigDecimal n:p)
            {
                //if(n>sqrti)
                    //break;
                if (i.remainder(n).equals( new BigDecimal(0)))
                {
                    prim = false;
                    break;
                }
            }
            if (prim)
            {
                p.add(i);
                System.out.println(i);
                //sn.nextLine();
               
            }

        }
    }
}
```
Ist allerdings überflüssig, da dieser Algorithmus ab gewisser Anzahl von Primzahlen ziemlich langsam wird. 
Vllt nimmt man ein grosses BigDecimal und sucht die nächsthöhere Primzahl...


----------



## stg (30. Okt 2016)

neoexpert hat gesagt.:


> Ich möchte demnächst RSA Algorithmus in Java machen. Da braucht man Riesiege Primzahlen. Wie bekommt man Primzahlen die mehrere hundert stellen haben?



Wenn dich das wirklich interessiert, dann solltest du das hier mal durcharbeiten:
http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf


----------



## Xyz1 (30. Okt 2016)

JStein52 hat gesagt.:


> BigDecimal !


Ich glaub, das war ein Gag, vermag das aber nicht zu sagen, denn



DerWissende hat gesagt.:


> , meine mathematischen Skillz sind für die Beantwortung dieser Frage nicht ausreichend.


----------



## Xyz1 (30. Okt 2016)

Mir ist noch aufgefallen, dass die Zeile so muss:

```
int sqrt = (int) Math.sqrt(i) ;
```

(+ 1 überflüssig)
Und hier sind die Primzahlen von 0 bis 10 000 000:
Anzahl 664 579, formatiert, passt gerade so in 1mb. 

Zum testen hatte ich die ersten 1 000 000 Primzahlen aus dem Internet, da stimmte alles


----------



## JStein52 (31. Okt 2016)

DerWissende hat gesagt.:


> Ich glaub, das war ein Gag


Das war durchaus kein Gag, damit rechne ich Pi auf beliebig viele Stellen genau aus. (wobei beliebig durch den vorhandenen Speicherplatz bzw. das Speichermodell (32 Bit / 64 Bit)  begrenzt wird). Und natürlich wird das dann langsam. Aber ich schaffe 5 Mio. Stellen in 40 Min.


----------



## JStein52 (31. Okt 2016)

Nochmal zu BigDecimal: ich hatte nicht gesehen dass er mit riesig bloss ein paar hundert Stellen meint.


----------



## stg (31. Okt 2016)

JStein52 hat gesagt.:


> Nochmal zu BigDecimal: ich hatte nicht gesehen dass er mit riesig bloss ein paar hundert Stellen meint.



"bloß" ?
Mit double oder long wird das jedenfalls nix


----------



## JStein52 (31. Okt 2016)

stg hat gesagt.:


> "bloß" ?


Sollte ein Gag sein


----------

