Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
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
Java:
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);
}
}
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.
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.
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.
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
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:
Java:
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!
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..
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...
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:
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:
Java:
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?
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).
