Das ist der beste Weg zur Umsetzung Primzahl finden, algorithmen in Java? Wie machen wir Klassen-Bibliothek und verwenden Sie dann in Java?

Ich möchte library-Klassen in Java und verwenden Sie in Zukunft meine Programme. Ich möchte diese library-Klassen zu finden, die Primzahlen bis zu einer bestimmten Anzahl oder sogar die nächste Primzahl oder man kann sagen, lösen die meisten die basic Dinge im Zusammenhang mit Primzahlen.

Ich noch nie eine Java-Bibliothek mit der Klasse. Mein Ziel ist es zu lernen, dies zu tun. Bitte helfen Sie mir, ohne, dass durch den Hinweis auf ein tutorial oder so etwas. Ich bin vertraut mit der netbeans IDE.
Ich fand heraus, ein paar algorithmen wie Sieb des Eratosthenes und Sieb des Atkin. Es wäre toll, wenn Sie zeigen können, noch ein paar mehr solche effizienten algorithmen. Ich will Sie nicht, der beste zu sein, aber zumindest gut genug. Mein Ziel ist es, zu lernen, einige Dinge umzusetzen. Weil ich wenig praktische Programmiererfahrung ich will es tun, um meine Fähigkeiten verbessern.
Mein Freund schlug mir vor, zu verwenden, Stream-Klassen, und er Sprach etwas über die Umsetzung, indem wir die Ausgabe einer Datei als Eingabe für ein anderes zu machen, meinen code rein. Ich wusste nicht, verstehen ihn sehr gut. Bitte verzeihen Sie mir, wenn ich nichts gesagt falsch. Was möchte ich Euch bitten, in diesem Punkt ist, ist, dass eine effiziente und OO Weg, das zu tun, was ich tun will. Wenn ja, bitte sagen Sie mir, wie zu tun, und wenn nicht bitte darauf hinweisen, auf eine andere Weise, es zu tun.

Ich habe Grundkenntnisse der Sprache Java. Was ich erreichen möchte durch dieses venture-Gewinn-coding-Erfahrung, weil das ist, was alle hier vermutet, "zu nehmen, kleine Dinge wie diese und lernen, auf meine eigenen"

danke an alle im Voraus

hinsichtlich

shahensha

BEARBEITEN:
In das Sieb des Eratosthenes und andere, die wir speichern müssen die zahlen von 2 bis n in eine Datenstruktur. Wo soll ich es speichern? Ich weiß, ich kann mit einer dynamischen Sammlung, aber nur eine kleine Frage...Wenn ich will, zum finden von Primzahlen in der Größenordnung von Milliarden oder noch mehr (ich werde Große ganze Zahl ohne Zweifel), aber all das wird gespeichert, in den Haufen richtig? Gibt es eine Angst vor dem überlauf? Selbst wenn es nicht klappt, wird es eine gute Praxis? Oder wäre es besser zum speichern der Telefonnummern oder der Liste (auf denen wir Aktionen ausführen, je nach Algorithmus) in eine Datei und access gibt es? Sorry, wenn meine Frage war zu noobish...

Mit "basic knowledge" von Java, IMHO sollte man nicht den Fokus vor allem auf der Suche nach den besten, effizientesten algorithmen, sondern in der Lage sein, um Sie umzusetzen. Ich würde einen Algorithmus und implementieren Sie ihn. Versuchen Sie dann die Umsetzung der anderen algorithmen als auch. Danach können Sie wählen, welche arbeiten das beste für Sie.
Ich denke, das sollten zwei Fragen. Eine über die Erstellung einer Bibliothek von Klassen und Erzeugung von Paketen. Die anderen, über die Implementierung ein Sieb in Java. Die zweite Frage ist wahrscheinlich schon beantwortet in einem älteren Beitrag (suchen, SO für Sieb des Eratosthenes).

InformationsquelleAutor shahensha | 2010-11-11

3

"Sieb des Eratosthenes" ist gut-Algorithmus zum finden von Primzahlen. Wenn Sie google verwenden, finden Sie bereit-Implementierung in java.

InformationsquelleAutor demas
2

Ich ' ll hinzufügen einige Gedanken zu diesem:
1. Es gibt nichts technisch unterschiedlich über eine Bibliothek-Klasse, es ist einfach, wie Sie es verwenden. Meiner Meinung nach, das wichtigste ist, dass Sie denken, hart über Ihre öffentliche API. Machen Sie es wenig genug, um nützlich zu sein, um Ihre potenziellen Anrufer, halten Sie es klein genug, dass Sie haben die Freiheit zu ändern, die interne Implementierung, wie Sie sehen, passen, und sicherzustellen, dass Sie haben ein gutes Verständnis von dem, was Ihre Bibliothek hat tun und was Sie nicht tun. Versuchen Sie nicht, alles zu tun, tun Sie nur eine Sache gut. (Und die API in der Regel erstreckt sich auch auf die Dokumentation zu, stellen Sie sicher, Sie schreiben menschenwürdige Javadocs.)
2. Starten Sie mit diesen, wie Sie sind in Ordnung. Wenn Sie entwerfen Sie Ihre API gut ist, können Sie diese Einstellung jederzeit ändern, und roll-out der version 1.1 verwendet einen anderen Algorithmus (oder sogar verwendet JNI aufrufen, eine native C-Bibliothek), und Ihre Anrufer können sich einfach fallen lassen in die neue JAR-Datei und verwenden Sie Ihren code sogar ohne Neukompilierung. Vergessen Sie nicht, dass die vorzeitige Optimierung ist die Wurzel allen übels; Mach dir keine sorgen Sie zu viel über Ihre erste version schnell, sondern konzentrieren sich auf die machen es richtig und machen es sauber.
3. Ich bin mir nicht sicher, warum Ihr Freund war, was darauf hindeutet streams. Streams sind eine Möglichkeit, den Umgang mit Eingabe und Ausgabe von raw-bytes - hilfreich beim Lesen von Dateien oder Netzwerk-verbindungen, aber in der Regel nicht ein guter Weg, um rufen Sie eine andere Java-Methode. Ihre Bibliothek sollte sich keine sorgen über Eingang und Ausgang, es muss nur bieten einige Methoden für numerische Berechnungen. So sollten Sie Methoden implementieren, die nehmen ganze zahlen (oder was auch immer angemessen ist) und zurück zahlen.
Beispielsweise, Sie in die Tat umsetzen können:
```
/**
 * Calculates the next prime number after a given point.
 *
 * Implementation detail: callers may assume that prime numbers are
 * calculated deterministically, such that the efficiency of calling
 * this method with a large parameter is not dramatically worse than
 * calling it with a small parameter.
 *
 * @param x The lower bound (exclusive) of the prime number to return.
 * Must be strictly positive.
 * @return Colloquially, the "next" prime number after the given parameter.
 * More formally, this number will be prime and there are no prime numbers
 * less than this value and greater than <code>x</code> that are also
 * prime.
 * @throws IllegalArgumentException if <code>x</code> is not strictly
 * positive.
 */
public long smallestPrimeGreaterThan(long x);

/**
 * Returns all prime numbers within a given range, in order.
 *
 * @param lowerBound The lower bound (exclusive) of the range.
 * @param upperBound The upper bound (exclusive) of the range.
 * @return A List of the prime numbers that are strictly between the
 * given parameters.  This list is in ascending order.  The returned
 * value is never null; if no prime numbers exist within the given
 * range, then an empty list is returned.
 */
public List<Long> primeNumbersBetween(long lowerBound, long upperBound);
```
Keine streams in Sicht! Verwendet von streams, wie z.B. die Ausgabe zu der Konsole, umgegangen werden soll, die von Anwendungen, die mit Ihrer Bibliothek und nicht durch Ihre Bibliothek selbst. Dies ist, was ich meinte in meinem ersten Punkt darum klar, was Ihre Bibliothek macht, und nicht tun. Sie einfach erzeugen der Primzahlen; es ist bis an den Aufrufer zu tun, dann etwas abkühlen lassen, mit Ihnen.

InformationsquelleAutor Andrzej Doyle
1

Aber wenn Sie vergleichen, das Sieb des Atkin ist schneller als das Sieb des Eratosthenes:

http://en.wikipedia.org/wiki/Prime_number_counting_function Siehe auch diesen link, wo die verschiedenen Funktionen sind einfach und verständlich erklärt 🙂

Glück..
- Ja, Sieb des Atkin ist schneller, aber es erfordert tiefere Kenntnisse der Mathematik.
InformationsquelleAutor LGAP
1
1. Gibt es keine solche Sache als "library class". Ich nehme an, du meinst, um eine Klasse in einer solchen Weise, ist es die Aufgabe in einer wiederverwendbaren Art und Weise. Die Art und Weise, dies zu tun ist, um eine saubere Schnittstelle - mit minimalem (wenn überhaupt) Bindungen zu anderen Bibliotheken oder zu Ihrer Ausführung Umgebung (deine main-Klasse etc).
2. Den beiden, die Sie erwähnen sind "gut genug". Für Ihre Zwecke müssen Sie nicht weiter suchen.
3. Nur Lesen aus dem System.in-und Schreibzugriff auf System.heraus und das ist es. Obwohl, in Ihrem Fall, es ist nichts zu Lesen.
Zu erreichen, was ich denke, ist Ihr Ziel, Sie müssen schreiben Sie eine main-Klasse, die hadles das execution-environment - main-Funktion initialisiert den Algorithmus, iterativ look für die nächste prime, und schreiben Sie es auf "System".aus. Natürlich müssen Sie eine weitere Klasse, die den Algorithmus implementieren. Es sollte enthalten den internen Zustand und bieten eine Methode zum Auffinden der nächsten Primzahl.

InformationsquelleAutor kresho

`IMO, halten beiseite die dachte, dass Sie eine Bibliothek (.jar-Datei, die nach meiner interpretation dieser Frage).

Fokus auf das erstellen eines einfachen Java-Klasse, die erste, wie hier:

//SieveOfEratosthenes.java
  public class PrimeSieve{
    public static void main(String args[])
    {
    int N = Integer.parseInt(args[0]);
             //initially assume all integers are prime
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

    //mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {

        //if i is prime, then mark multiples of i as nonprime
        //suffices to consider mutiples i, i+1, ..., N/i
        if (isPrime[i]) {
            for (int j = i; i*j <= N; j++) {
                isPrime[i*j] = false;
            }
        }
    }

    //count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) primes++;
    }
    System.out.println("The number of primes <= " + N + " is " + primes);
}
}

Nun, der nächste Schritt; Umsetzung für größere Werte, Sie können immer mit BigInteger. SO Fragen die gleichen:

Lesen Sie alle Fragen im Zusammenhang mit BigInteger-Klasse auf, SO, BigInteger Tagged Fragen.

Hoffe, das hilft.

InformationsquelleAutor ykombinator

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.