Primzahl in einem Array finden

[Sansibar007]

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]

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]

ok Danke ich versuchs mal

 

[Landei]

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]

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]

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]

@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]

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]

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]

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]

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!
😀

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]

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]

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]

Nimm doch Landei's Algorithmus!

Der ist effizient

(und das sogar ganz ohne Ironie 😀)

 

[Shulyn]

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]

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]

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]

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]

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]

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]

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]

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).