# Primzahl in einem Array finden



## Sansibar007 (31. Aug 2009)

Hallo, 
ich wollte versuchen die Primzahlen in einem Array auszugeben, leider macht es nicht was es machen soll... hat jemand eine Idee, wo der Fehler sein könnte?

und wenn es dann klappt, wie kriege ich die Nullen aus dem neuen Array?

Vielen Dank im Voraus


```
public class Prim {

    static void p(int[] a){
            int[] b=new int[a.length];
            int count = 0;
        for(int i=0;i<a.length;i++){
            if(a[i]%2!=0 || a[i]%3!=0){
                b[i]=a[i];
                count++;
            }
        }
          System.out.println(java.util.Arrays.toString(b));
    }

    public static void main(String[] args){
        int[] a={2,4,7,13,24,7};
        p(a);
    }


}
```


----------



## bygones (31. Aug 2009)

abgesehen davon dass dein Test auf eine Primzahl mit 2 und 3 nicht wirklich der realitaet entspricht ist das hauptproblem dennoch dieser vgl.

ueberleg mal was mit der Zahl 2 passiert [c]a_%2!=0 || a%3!=0[/c] ... %2 gibt natuerlich 0, %3 != 0... ergo geht er in den if zweig und fuegt 2 hinzu.

wie gesagt - such mal im forum, da gibts schon zig primzahl algorithmen_


----------



## Sansibar007 (31. Aug 2009)

ok Danke ich versuchs mal


----------



## Landei (31. Aug 2009)

Es gibt schon ein BigInteger.isProbablyPrime oder so. Für Zahlen im long-Bereich ist die Funktion immer  korrekt (nur bei größeren gibt es eine mikroskopische Chance, dass sie danebenliegt), und außerdem sehr effizient.


----------



## ARadauer (31. Aug 2009)

Landei hat gesagt.:


> Es gibt schon ein BigInteger.isProbablyPrime oder so. Für Zahlen im long-Bereich ist die Funktion immer  korrekt (nur bei größeren gibt es eine mikroskoipische Chance, dass sie danebenliegt), und außerdem sehr effizient.



bezweifle das der Threadsteller das benutzen darf... vermute, dass es eine Aufgabe ist...


----------



## Landei (31. Aug 2009)

Na gut... ausm'm Kopp und ohne Gewähr:

```
public class Prim {
    static boolean isPrime(n:int) {
       if(n == 2) return true;
       if(n < 2 || n % 2 == 0) return false;
       for(int i = 3; i*i <= n; i +=2) {
          if (n % i == 0) return false;
       } 
       return true;
    } 

    static void p(int[] a){
        for(int i=0; i<a.length; i++){
            if(isPrime(a[i])){
                System.out.print("" + a[i] + ",");
            }
        }
    }
 
    public static void main(String[] args){
        int[] a={2,4,7,13,24,7};
        p(a);
    }
 
}
```


----------



## Sansibar007 (31. Aug 2009)

@ARadauer   richtig erkannt

ich habe jetzt vielleicht eine neuen Ansatz: Ich rechne erstmal den ggt aus und prüfe dann, ob er größer als 2 ist


@Landei   vielen Dank für deine Mühe!


----------



## Landei (31. Aug 2009)

Mit dem ggt bekommts du keine Primzahlen raus. ggt(25,18) == 1, aber was nützt dir das jetzt? Beide Zahlen sind relativ prim, aber keine Primzahlen...


----------



## Leroy42 (31. Aug 2009)

Du teilst ja eventuell durch jede Zahl.

Obwohl du nur durch Primzahlen zu teilen versuchen müßtest:


```
public  boolean isPrim(int n) {
		if (n<2) 
			return false; 
		int anzTeiler = 0; 
		for (int kandidat=2; kandidat < n; kandidat++) 
			if (isPrim(kandidat) && n%kandidat == 0) 
				++anzTeiler; 
		return anzTeiler == 0; 
	}
```

Sicher 'ne wahnsinnige Effizienzsteigerung!


----------



## Shulyn (31. Aug 2009)

> if(a_%2!=0 || a%3!=0)
> _


_
Dein Algorithmus ist nicht so das wahre. Schreibe dir nocheinaml auf was zutreffen muss /nicht muss damit es eine Primzahl ist.

Warum willst du den die 0en aus deinem Array entfernen? Du kannst sie Z.b bei der Ausgabe einfach ignorieren (if (b != 0)  ) ...

Eine möglichkeit um bestimmte einträge aus einem Array "zu löschen" ist es ein neues Array zu erstellen und dort nur die gewünschten einträge hineinzuschreiben.

Shu!_


----------



## Landei (31. Aug 2009)

Leroy42 hat gesagt.:


> Du teilst ja eventuell durch jede Zahl.
> 
> Obwohl du nur durch Primzahlen zu Teilen versuchen müßtest:
> 
> ...



Ganz bestimmt nicht:
- man braucht nur Teiler bis sqrt(n) zu testen
- man kann gerade Teilerkandidaten überspringen
- das rekursive isPrim()-Aufgerufe braucht mit Sicherheit mehr Zeit als ein einfaches % (wenn schon, dann müsste man die Primzahlen cachen, und dann könnte man sie z.B. mit dem Sieb des Eratosthenes effizient berechnen)
- wozu zählst du die Anzahl Teiler? Nachdem man den ersten gefunden hat, ist die Antwort doch klar


----------



## Leroy42 (31. Aug 2009)

Mach' mir mein Algorithmus doch nicht madig! ;(


```
public class Primzahlen {
	static long aufrufe;
	
	public static boolean isPrim(int n) {
		++aufrufe;
		if (n<2) 
			return false; 
		int anzTeiler = 0; 
		for (int kandidat=2; kandidat < n; kandidat++) 
			if (isPrim(kandidat) && n%kandidat == 0) 
				++anzTeiler; 
		return anzTeiler == 0; 
	}	
	
	public static int d(int n) {
		int sum=0;
		for (int i=1; i <= n; i++)
			if (isPrim(i) && n%i == 0)
				sum += i;
		return sum;
	}
	
	public static void main(String[] args) {
		long time = System.currentTimeMillis();
		System.out.println("d(30)="+d(30) +"(geschmeidige " +aufrufe + " Aufrufe) : Zeit in ms:"+(System.currentTimeMillis()-time));
	}
}
```

Ausgabe:

```
d(30)=10(geschmeidige 536870912 Aufrufe) : Zeit in ms:13813
```

Alle Zahlen bis 30 auf Primitivität prüfen: Nur 14 Sekunden und 536.870.912 Aufrufe!

Wer kann's schneller?


----------



## Sansibar007 (31. Aug 2009)

Dachte das so mit dem ggt... aber scheint whol ein doofer Ansatz gewesen zu sein 



```
static int größterTeiler(int i) {
int j = i / 2;
while ( i % j != 0 ) {
j--;
}
return j;
}



static boolean prim(int i) {
if (i >= 2 && größterTeiler(i) == 1)
return true;
else
return false;
```


----------



## Leroy42 (31. Aug 2009)

Nimm doch Landei's Algorithmus!

Der ist effizient

(und das sogar ganz ohne Ironie )


----------



## Shulyn (1. Sep 2009)

Sansibar007 hat gesagt.:


> Dachte das so mit dem ggt... aber scheint whol ein doofer Ansatz gewesen zu sein


von Die Primzahlseite

Zur Gewinnung der Primfaktorzerlegung geht man gewöhnlich die Primzahlen von unten (d.h. 2, 3, 5, 7...) durch und prüft, ob die zu zerlegende Zahl durch sie ohne Rest glatt teilbar ist. In diesem Fall schreibt man die Primzahl auf, teilt die zu zerlegende Zahl durch die Primzahl und macht mit dem Ergebnis (dem Quotienten) weiter, bis am Schluß nur noch eine Primzahl übrig bleibt.

Beispiel: 2394 soll in Primfaktoren zerlegt werden. 2394 ist durch 2 teilbar, also: eine 2 gemerkt und 2394:2=1197 berechnen. 1197 ist nicht mehr durch 2, aber durch 3 teilbar. 3 merken, Quotient: 1197:3=399. 399 ist nochmal durch 3 teilbar: die zweite 3 merken, Quotient: 133. Das ist nicht mehr durch 3 und nicht durch 5, aber durch die 7 teilbar. 7 merken; 133:7=19. Das ist eine Primzahl, d.h. die Primfaktorzerlegung ist gefunden mit 2394=2·3·3·7·19 oder 2·32·7·19.


So kannst du auch auf Primzahlen prüfen. Ob es der beste weg ist.. ka... denke da eher in die richtung  "Sieb des Eratosthenes" ist aber nicht so einfach zu implementieren..


----------



## FatFire (1. Sep 2009)

> denke da eher in die richtung "Sieb des Eratosthenes" ist aber nicht so einfach zu implementieren..


Rofl? Oder geht das jetzt nur mir so?

Gruß FatFire


----------



## Landei (1. Sep 2009)

LOL, ich auch. Aus'm Kopp und ohne Gewähr:

```
int[] numbers = new int[1000];
for(int i = 0; i < numbers.length; i++) {
   numbers[i] = i;
}
numbers[1] = 0;
for(int i = 2; i < numbers.length; i++) {
  if (numbers[i] != 0) {
    for(int j = 2*i; j < numbers.length; j += i) {
       numbers[j] = 0;
    }
  }
}
List<Integer> primes = new ArrayList<Integer>();
for(int i : numbers) {
  if (i != 0) {
      primes.add(i);
  }
}
```

Man kann das Sieb übrigens auch so implementieren, dass es beliebig weit läuft (siehe eSCALAtion BLOG Artikel "Mit sieben Sieben sieben").


----------



## Shulyn (1. Sep 2009)

FatFire hat gesagt.:


> Rofl? Oder geht das jetzt nur mir so?
> 
> Gruß FatFire


:bloed:

Hmm wenn ich in einem Thema Antworte gehe ich nicht davon aus das sich ALLE angesprochen fühlen sollten. Für jemanden der gerade Java lernt, also seine 1. Schritte macht (Am anfang bekommt man meist die Aufgabe mit den Primzahlen), denke ich schon das es nicht Einfach ist "mal eben" Sieb des Eratosthenes zu schreiben.

Das man nach ka 5 Jahren Java erfahrung, oder evtl Mehjähriger Berufserfahrung als Java-Entwickler, das können muss ist mir schon klar... 

So genug Offtopic für heute...


----------



## ARadauer (1. Sep 2009)

> denke ich schon das es nicht Einfach ist "mal eben" Sieb des Eratosthenes zu schreiben.


naja muss ja nicht einfach sein. Das ist Integral Rechnung auch nicht... und trotzdem kann man es von einem Schüler/Student erwarten..


Also ich denke schon, dass das Sieb des Eratosthenes eine gerechtfertigte Aufgabe für die ersten Stunden des ersten Semesters sind...


----------



## 0x7F800000 (1. Sep 2009)

Shulyn hat gesagt.:


> Das man nach ka 5 Jahren Java erfahrung, oder evtl Mehjähriger Berufserfahrung als Java-Entwickler, das können muss ist mir schon klar...


Die Tatsache dass der Algo nur Addition von ganzen Zahlen voraussetzt und seit paar tausend Jahren bekannt ist spricht aber nicht gerade für Komplexität  Das ist überhaupt einer der ältesten und einfachsten Algorithmen, der überhaupt etwas korrektes liefert^^ Mit 5 Jahren Java erfahrung ist man da jedenfalls hoffnungslos überqualifiziert. :autsch:


----------



## FatFire (1. Sep 2009)

Also das Sieb ist nur ne Fingerübung für einen erfahrenen Programmierer, das stimmt. Aber es ist aufgrund der verwendeten Kenntnisse (einfach verschachtelte For-Schleife, meist ein boolean-Array und irgendeine Möglichkeit die Ergebnisse rauszuschmeissen) ein typisches Problem vor dessen Implementierung man auch als Anfänger keine Angst haben darf! Sonst ist das so, als möchte einer Schreiner lernen und sagen: "Naja, also im ersten Lehrjahr fasse ich aber keinen Hammer und keine Säge an, ich könnte ja was kaputtmachen oder mich verletzen.".
So, und ich will natürlich nicht nur dumm labern:

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Prim {

	public static boolean[] getSieb(int ende) {
		ende++;
		boolean[] sieb = new boolean[ende];
		for (int i = 2; i < ende; i++)
			sieb[i] = true;
		int endeWurzel = (int) Math.sqrt(ende);
		for (int i = 2; i < endeWurzel; i++)
			if (sieb[i])
				for (int j = i * 2; j < ende; j += i)
					sieb[j] = false;
		return sieb;
	}

	public static void main(String[] args) {
		int[] a = { 2, 4, 7, 13, 24, 7 };
		int siebMax = Integer.MIN_VALUE;
		for (int i : a)
			if (i > siebMax)
				siebMax = i;
		boolean[] sieb = getSieb(siebMax);
		List<Integer> primzahlen = new ArrayList<Integer>();
		for (int i : a)
			if (sieb[i] && !primzahlen.contains(i))
				primzahlen.add(i);
		Integer[] primzahlenArray = primzahlen.toArray(new Integer[primzahlen
				.size()]);
		System.out.println(Arrays.toString(primzahlenArray));
	}

}
```
Das wäre jetzt auf Basis des Siebs implementiert (obwohl mir die ziemlich am Anfang von Landei gezeigte Variante auch besser gefällt). Jedenfalls am Ende keine leeren Plätze und doppelten Einträge im Array primzahlenArray, das Array kann noch weiter benutzt werden (also nicht einfach nur Ausgabe "ist Prim" und schon ist die Information flöten) und auch ansonsten bin ich der Geilste :lol:
So, jetzt macht mir in der Zeit bis Sansibar mal erzählt, wie er es nun implementiert hat, noch ein wenig mein Prog oder meinen Beitrag madig :toll:

Gruß FatFire

PS: Hat einer eine Ahnung ob es schneller ist, eine ArrayList anzulegen, die zu füllen und dann in ein normales Array zu wandeln oder einmal drüber laufen, dabei zählen wieviele Primzahlen vorhanden sind und diese dann in einem zweiten Anlauf erst in dem Array zu plazieren?


----------



## Landei (1. Sep 2009)

FatFire hat gesagt.:


> PS: Hat einer eine Ahnung ob es schneller ist, eine ArrayList anzulegen, die zu füllen und dann in ein normales Array zu wandeln oder einmal drüber laufen, dabei zählen wieviele Primzahlen vorhanden sind und diese dann in einem zweiten Anlauf erst in dem Array zu plazieren?


Im array nach vorn verschieben, und dann ein arrayCopy in ein Array mit der richtigen Größe.

Wenn man eine ArrayList nimmt, gleich mit der ungefähr richtigen Größe anlegen. Der Trick ist nämlich, dass man ziemlich genau weiß, wieviel Primzahlen es von 1 bis n gibt, nämlich etwa n/ln(n).


----------

