Πιο αποτελεσματικό κώδικα για τα πρώτα 10.000 πρώτοι αριθμοί;

ψήφοι
49

Θέλω να εκτυπώσετε τα πρώτα 10000 πρώτοι αριθμοί. Μπορεί κάποιος να μου δώσει την πιο αποδοτικό κώδικα για αυτό; διευκρινίσεις:

  1. Δεν έχει σημασία αν ο κωδικός σας είναι αναποτελεσματική για n> 10000.
  2. Το μέγεθος του κώδικα δεν έχει σημασία.
  3. Δεν μπορείτε απλά δύσκολο κωδικοποιήσει τις τιμές με οποιονδήποτε τρόπο.
Δημοσιεύθηκε 03/08/2008 στις 06:45
πηγή χρήστη
Σε άλλες γλώσσες...                            


28 απαντήσεις

ψήφοι
41

Το Κόσκινο του Atkin είναι ίσως αυτό που ψάχνετε, ανώτερο όριο χρόνου λειτουργίας του θα είναι O (N / log log N).

Αν τρέχετε μόνο τους αριθμούς 1 ολοένα και 1 μικρότερο από τα πολλαπλάσια του 6, θα μπορούσε να είναι ακόμη πιο γρήγορα, όπως όλοι οι πρώτοι αριθμοί πάνω από το 3 είναι 1 μακριά από κάποιο πολλαπλάσιο του έξι. Πόρων για τη δήλωσή μου

Απαντήθηκε 03/08/2008 στις 07:03
πηγή χρήστη

ψήφοι
35

Θα ήθελα να συστήσω ένα κόσκινο, είτε το Κόσκινο του Ερατοσθένη ή το κόσκινο του Atkin.

Το κόσκινο ή Ερατοσθένη είναι ίσως το πιο έξυπνο τρόπο για την εξεύρεση μια λίστα των πρώτων αριθμών. Βασικά σας:

  1. Γράψτε κάτω μια λίστα με τους αριθμούς από 2 σε ό, τι όριο που θέλετε, ας πούμε 1000.
  2. Πάρτε τον πρώτο αριθμό που δεν διασχίζεται από (για την πρώτη επανάληψη είναι 2) και διαγράφω όλα τα πολλαπλάσια του αριθμού αυτού από τη λίστα.
  3. Επαναλάβετε το βήμα 2 μέχρι να φτάσετε στο τέλος της λίστας. Όλοι οι αριθμοί που δεν έχουν περάσει από τα prime.

Προφανώς υπάρχουν αρκετές βελτιστοποιήσεις που μπορούν να γίνουν για να κάνουν αυτό το έργο αλγόριθμο πιο γρήγορα, αλλά αυτή είναι η βασική ιδέα.

Το κόσκινο του Atkin χρησιμοποιεί μια παρόμοια προσέγγιση, αλλά, δυστυχώς, δεν ξέρω αρκετά για να σας το εξηγήσω. Αλλά εγώ ξέρω ότι ο αλγόριθμος που συνδέεται διαρκεί 8 δευτερόλεπτα για να καταλάβω όλες τις πρώτους έως 1000000000 πάνω σε αρχαίο Pentium II-350

Κόσκινο του Ερατοσθένη πηγαίου κώδικα: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Κόσκινο του Atkin πηγαίου κώδικα: http://cr.yp.to/primegen.html

Απαντήθηκε 06/08/2008 στις 00:49
πηγή χρήστη

ψήφοι
17

Αυτό δεν είναι αυστηρά σε σχέση με τον περιορισμό ενσωματώνουμε, αλλά έρχεται τρομερά κοντά. Γιατί να μην κάνετε λήψη κάποιου προγράμματος αυτήν τη λίστα και να το τυπώσετε έξω, αντ 'αυτού;

http://primes.utm.edu/lists/small/10000.txt

Απαντήθηκε 31/08/2008 στις 23:20
πηγή χρήστη

ψήφοι
11

GateKiller , πώς για την προσθήκη ενός breakμε εκείνη ifστο foreachβρόχο; Αυτό θα επιταχύνει τα πράγματα πολύ , διότι αν, όπως 6 διαιρείται με το 2 δεν χρειάζεται να ελέγξει με 3 και 5. (θα ήθελα να ψηφίσω λύση σας έτσι κι αλλιώς, αν είχα αρκετή φήμη :-) ...)

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}
Απαντήθηκε 27/08/2008 στις 21:26
πηγή χρήστη

ψήφοι
9

Στο Haskell, μπορούμε να γράψετε σχεδόν λέξη προς λέξη το μαθηματικό ορισμό του κόσκινου του Ερατοσθένη, « πρώτων αριθμών είναι φυσικοί αριθμοί πάνω από 1 χωρίς σύνθετων αριθμών, όπου τα σύνθετα υλικά που βρέθηκαν από την απαρίθμηση των πολλαπλασίων κάθε προνομιακή του »:

primes = 2 : minus [3..] (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) 
                                [] primes)

primes !! 10000 είναι σχεδόν στιγμιαία.

Βιβλιογραφικές αναφορές:


Ο παραπάνω κώδικας είναι εύκολα πειραγμένο στην αγορά εργασίας μόνο σε πιθανότητες, primes = 2:3:minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). Χρονικής πολυπλοκότητας είναι πολύ βελτιωμένη (ακριβώς για ένα αρχείο καταγραφής παράγοντα παραπάνω βέλτιστη) με δίπλωση του σε ένα δέντρο που μοιάζει με τη δομή, και το διάστημα πολυπλοκότητα δραστικά βελτιώνεται με πολλαπλά στάδια παραγωγής πρώτων αριθμών , σε

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p-> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

(Σε Haskell οι παρενθέσεις χρησιμοποιούνται για την ομαδοποίηση, μια κλήση της συνάρτησης είναι καθοριζόταν μόνο από παράθεση, (:)είναι ένα μειονεκτήματα χειριστή για τους καταλόγους, και (.)είναι ένα λειτουργικό φορέα σύνθεση: (f . g) x = (\y-> f (g y)) x = f (g x)).

Απαντήθηκε 24/04/2012 στις 17:30
πηγή χρήστη

ψήφοι
9

@Matt: log (log (10000)) είναι ~ 2

Από το άρθρο της Wikipedia (η οποία θα αναφέρεται) Κόσκινο του Atkin :

Αυτό κόσκινο υπολογίζει πρώτους μέχρι Ν χρησιμοποιώντας O(N/log log N)λειτουργίες με μόνο Ν 1/2 + o (1) bits της μνήμης. Αυτό είναι λίγο καλύτερο από το κόσκινο του Ερατοσθένη που χρησιμοποιεί O(N) λειτουργίες και O (N 1/2 (log log N) / log N) bits της μνήμης (AOL Atkin, DJ Bernstein, 2004) . Αυτές ασυμπτωτική υπολογιστική πολυπλοκότητα περιλαμβάνουν απλά βελτιστοποιήσεις, όπως παραγοντοποίηση τροχό, και τη διάσπαση του υπολογισμού σε μικρότερα μπλοκ.

Δεδομένου ασυμπτωτική υπολογιστική πολυπλοκότητα μαζί O(N)(για Ερατοσθένης) και O(N/log(log(N)))(για Atkin) δεν μπορούμε να πούμε (για μικρά N=10_000) η οποία αλγόριθμο, αν εφαρμοστούν, θα είναι ταχύτερη.

Achim Flammenkamp έγραψε το κόσκινο του Ερατοσθένη :

που παραθέτει:

@ NUM1

Για διαστήματα μεγαλύτερα περίπου 10 ^ 9, σίγουρα για εκείνους> 10 ^ 10, το Κόσκινο του Ερατοσθένη είναι πολύ καλύτερες επιδόσεις από το κόσκινο της Atkins και Bernstein η οποία χρησιμοποιεί αμείωτη δυαδικό τετραγωνικές μορφές. Δείτε το χαρτί τους για πληροφορίες υποβάθρου, καθώς και της παραγράφου 5 του Δρ W. του Galway ΠΤΥΧΙΑΚΗ ΕΡΓΑΣΙΑ.

Ως εκ τούτου για 10_000Κόσκινο του Ερατοσθένη μπορεί να είναι ταχύτερη τότε Κόσκινο του Atkin.

Για να απαντήσετε ΕΠ ο κωδικός prime_sieve.c (αναφέρεται από num1)

Απαντήθηκε 06/10/2008 στις 21:03
πηγή χρήστη

ψήφοι
7

Χρησιμοποιώντας GMP, θα μπορούσε κανείς να γράψει τα εξής:

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

Σε 2.33GHz μου Macbook Pro, εκτελεί τα εξής:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Υπολογισμός 1.000.000 πρώτοι στον ίδιο φορητό υπολογιστή:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP είναι ιδιαίτερα αισιόδοξος για αυτό το είδος του πράγματος. Αν δεν θέλετε πραγματικά να κατανοήσουμε τους αλγόριθμους γράφοντας τη δική σας, θα πρέπει να συμβουλεύονται να χρησιμοποιούν libGMP υπό C.

Απαντήθηκε 29/08/2008 στις 08:06
πηγή χρήστη

ψήφοι
4

Έχω προσαρμοστεί κώδικα που βρέθηκαν στο CodeProject για να δημιουργήσετε το παρακάτω:

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

Δοκιμή αυτό στο ASP.NET μου διακομιστή πήρε το rountine περίπου 1 λεπτό για να τρέξει.

Απαντήθηκε 05/08/2008 στις 20:55
πηγή χρήστη

ψήφοι
4

Δεν είναι αποτελεσματική σε όλους, αλλά μπορείτε να χρησιμοποιήσετε μια κανονική έκφραση για να ελέγξετε για πρώτους αριθμούς.

/^1?$|^(11+?)\1+$/

Αυτό ελέγχει εάν, για μια σειρά που αποτελείται από k « 1» s, k είναι Not Prime (δηλαδή εάν η συμβολοσειρά αποτελείται από ένα « 1» ή οποιοδήποτε αριθμό των « 1» s που μπορεί να εκφραστεί ως ένα n -ary προϊόντος).

Απαντήθηκε 03/08/2008 στις 19:52
πηγή χρήστη

ψήφοι
3

Εδώ είναι ένα κόσκινο του Ερατοσθένη που έγραψα στο PowerShell πριν από λίγες ημέρες. Έχει μια παράμετρο για τον προσδιορισμό του αριθμού των πρώτων αριθμών που θα πρέπει να επιστραφούν.

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}
Απαντήθηκε 07/09/2009 στις 19:52
πηγή χρήστη

ψήφοι
3

Κόσκινο του Ερατοσθένη είναι ο τρόπος να πάει, λόγω του ότι είναι η απλότητα και την ταχύτητα. Εφαρμογή μου σε C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    unsigned int lim, i, j;

    printf("Find primes upto: ");
    scanf("%d", &lim);
    lim += 1;
    bool *primes = calloc(lim, sizeof(bool));

    unsigned int sqrtlim = sqrt(lim);
    for (i = 2; i <= sqrtlim; i++)
        if (!primes[i])
            for (j = i * i; j < lim; j += i)
                primes[j] = true;

    printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
    for (i = 2; i < lim; i++)
        if (!primes[i])
            printf("%d\n", i);

    return 0;
}

CPU Ώρα να βρούμε πρώτους αριθμούς (για Pentium Dual Core E2140 1,6 GHz, χρησιμοποιώντας ενιαίο πυρήνα)

~ 4s για lim = 100.000.000

Απαντήθηκε 21/08/2008 στις 00:45
πηγή χρήστη

ψήφοι
2

Η deque αλγόριθμο κόσκινο αναφέρει BenGoldberg αξίζει μια πιο προσεκτική ματιά, όχι μόνο επειδή είναι πολύ κομψό, αλλά και επειδή μπορεί μερικές φορές να είναι χρήσιμο στην πράξη (σε αντίθεση με το κόσκινο του Atkin, η οποία είναι μια καθαρά ακαδημαϊκή άσκηση).

Η βασική ιδέα πίσω από το deque αλγόριθμο κόσκινο είναι να χρησιμοποιήσετε ένα μικρό, συρόμενη σήτα που είναι αρκετά μεγάλο μόνο για να περιέχει τουλάχιστον ένα ξεχωριστό πολλαπλά για κάθε μία από τις επί του παρόντος «ενεργών» πρωταρχικούς παράγοντες - δηλαδή των πρώτων αριθμών των οποίων η πλατεία δεν υπερβαίνει το χαμηλότερο αριθμό σήμερα εκπροσωπείται από τον κινούμενο κόσκινο. Μια άλλη διαφορά στο SOE είναι ότι οι deque καταστήματα κόσκινο τα πραγματικά στοιχεία μέσα στις σχισμές των σύνθετων υλικών, δεν booleans.

Ο αλγόριθμος επεκτείνει το μέγεθος του παραθύρου κόσκινου όπως απαιτείται, καταλήγοντας σε αρκετά ακόμη απόδοση σε μία ευρεία περιοχή μέχρι το κόσκινο ξεκινά υπερβαίνει την ικανότητα του L1 cache της CPU αισθητά. Το τελευταίο κύριος που ταιριάζει απόλυτα είναι 25.237.523 (ο κύριος 1,579,791st), η οποία δίνει μια γενική εικόνα εξέδρα για το εύλογο εύρος λειτουργίας του αλγορίθμου.

Ο αλγόριθμος είναι αρκετά απλή και ισχυρή, και έχει ακόμη και απόδοση σε ένα πολύ ευρύτερο φάσμα από ένα μη κατατετμημένο Κόσκινο του Ερατοσθένη. Το τελευταίο είναι πολύ πιο γρήγορα όσο κόσκινο του ταιριάζει απόλυτα στο χώρο προσωρινής αποθήκευσης, δηλαδή έως και 2 ^ 16 για ένα στοίχημα μόνο κόσκινο με byte μεγέθους bools. Στη συνέχεια απόδοσή του πέφτει όλο και περισσότερο, αν και παραμένει πάντα πολύ πιο γρήγορα από ό, τι το deque παρά το μειονέκτημα (τουλάχιστον σε καταρτίζονται γλώσσες όπως η C / C ++, Pascal ή Java / C #).

Εδώ είναι μια απόδοση της deque αλγόριθμου κόσκινο σε C #, διότι θεωρώ ότι η γλώσσα - παρά τις πολλές αδυναμίες της - πολύ πιο πρακτικό για τους αλγόριθμους πρωτοτύπων και πειραματισμό από το εξαιρετικά δυσκίνητο και σχολαστικός C ++. (Υποσημείωση: Είμαι χρησιμοποιώντας το δωρεάν LINQPad που επιτρέπει να βουτήξει δεξιά, χωρίς όλα τα ακαταστασία με τη δημιουργία έργων, makefiles, καταλόγους ή οτιδήποτε, και μου δίνει τον ίδιο βαθμό διαδραστικότητας ως προτροπή python).

C # δεν έχει ρητή τύπου deque αλλά το απλό List<int>λειτουργεί αρκετά καλά για την επίδειξη του αλγορίθμου.

Σημείωση: αυτή η έκδοση δεν χρησιμοποιεί μια αμφίδρομη δομή δεδομένων για τους πρώτους, διότι απλά δεν έχει νόημα να σκάσει από sqrt (n) από n πρώτων αριθμών. Τι καλό θα ήταν να αφαιρέσει το 100 πρώτων αριθμών και να φύγουν 9900; Τουλάχιστον αυτό τον τρόπο όλες οι πρώτων αριθμών που συλλέγονται σε ένα τακτοποιημένο φορέα, έτοιμο για περαιτέρω επεξεργασία.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

Εδώ είναι οι δύο βοηθητικές λειτουργίες:

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

Πιθανώς ο ευκολότερος τρόπος για την κατανόηση του αλγορίθμου είναι να το φανταστούμε ως ειδική τμηματική Κόσκινο του Ερατοσθένη με μέγεθος τμήμα 1, συνοδευόμενη από μια περιοχή υπερχείλισης, όπου οι πρώτοι έρχονται να ξεκουραστούν, όταν πυροβολούν πάνω από το άκρο του τμήματος. Εκτός από το ότι το μόνο κύτταρο του τμήματος (aka sieve[0]) έχει ήδη κοσκινισμένο όταν φτάσουμε σε αυτό, γιατί έχεις τρέξει πάνω, ενώ ήταν μέρος της περιοχής υπερχείλισης.

Ο αριθμός που αντιπροσωπεύεται από sieve[0]διατηρείται σε sieve_base, αν sieve_frontκαι window_baseθα ήταν επίσης μια καλή ονόματα που επιτρέπουν σε παραλληλισμούς με τον κωδικό του Ben ή εφαρμογές τμηματική / παράθυρα κόσκινα.

Εάν sieve[0]περιέχει μια μη-μηδενική τιμή, τότε η τιμή αυτή είναι ένας παράγοντας του sieve_base, η οποία μπορεί έτσι να αναγνωριστεί ως σύνθετα. Από το κελί 0 είναι πολλαπλάσιο αυτού του παράγοντα είναι εύκολο να υπολογιστεί το επόμενο hop, η οποία είναι απλώς 0 συν το στοιχείο αυτό. Πρέπει να καταληφθεί ήδη από άλλον παράγοντα που κυττάρου, τότε απλά προσθέστε τον παράγοντα και πάλι, και ούτω καθεξής μέχρι να βρούμε ένα πολλαπλάσιο του παράγοντα, όπου κανένας άλλος παράγοντας είναι σήμερα σταθμευμένο (επέκταση του κόσκινου, αν χρειαστεί). Αυτό σημαίνει επίσης ότι δεν υπάρχει ανάγκη για την αποθήκευση των σημερινών μετατοπίσεις της λειτουργίας των διαφόρων πρώτων αριθμών από το ένα τμήμα στο άλλο, όπως σε ένα κανονικό κατακερματισμένη κόσκινο. Όποτε βρίσκουμε έναν παράγοντα για την sieve[0], σημερινή της που εργάζονται μετατόπιση είναι 0.

Η σημερινή προνομιακή μπαίνει στο παιχνίδι με τον ακόλουθο τρόπο. Ένα χαρακτηριστικό μπορεί να γίνει μόνο μετά από δική τρέχουσα εμφάνισή του στο ρεύμα (δηλαδή όταν έχει εντοπιστεί ως κύριος, επειδή δεν σημειώνονται με συντελεστή), και θα παραμείνει τρέχουσα, μέχρι την ακριβή στιγμή που sieve[0]φτάνει πλατεία. Όλα τα χαμηλότερα πολλαπλάσια αυτής της πρωταρχικής πρέπει να έχει διαγραφεί λόγω των δραστηριοτήτων των μικρότερων πρώτων αριθμών, ακριβώς όπως σε ένα κανονικό κρατικών επιχειρήσεων. Αλλά κανένας από τους μικρότερους πρώτων αριθμών μπορεί να χτυπήσει από την πλατεία, αφού ο μόνος παράγοντας της πλατείας είναι η πρωταρχική τον εαυτό της και δεν είναι ακόμη σε κυκλοφορία σε αυτό το σημείο. Αυτό εξηγεί τις ενέργειες που λαμβάνονται από τον αλγόριθμο στην υπόθεση sieve_base == current_prime_squared(η οποία συνεπάγεται sieve[0] == 0, από τον τρόπο).

Τώρα η υπόθεση sieve[0] == 0 && sieve_base < current_prime_squaredείναι εύκολο να εξηγηθεί: αυτό σημαίνει ότι sieve_baseδεν μπορεί να είναι πολλαπλάσιο του οποιοδήποτε από τα primes μικρότερη από την τρέχουσα κύρια, ή αλλιώς θα είχαν επισημανθεί ως σύνθετα. Δεν μπορεί να είναι ανώτερο πολλαπλάσιο του σημερινού προνομιακή είτε, αφού η αξία του είναι μικρότερη από την πλατεία του τρέχοντος προνομιακή του. Ως εκ τούτου, πρέπει να είναι μια νέα prime.

Ο αλγόριθμος είναι προφανώς εμπνευσμένο από το κόσκινο του Ερατοσθένη, αλλά εξίσου προφανώς είναι πολύ διαφορετική. Το κόσκινο του Ερατοσθένη αντλεί ανώτερη ταχύτητα της από την απλότητα των στοιχειωδών λειτουργιών της: ένα ενιαίο προσθήκη δείκτη και ένα κατάστημα για κάθε βήμα της πράξης είναι όλα ότι το κάνει για μεγάλα χρονικά διαστήματα.

Εδώ είναι μια απλή, μη κατατετμημένο Κόσκινο του Ερατοσθένη που συνήθως χρησιμοποιούν για κοσκίνισμα πρώτων αριθμών παράγοντα στην περιοχή ushort, δηλαδή μέχρι 2 ^ 16. Για τη θέση αυτή έχω τροποποιηθεί για να εργαστούν πέραν του 2 ^ 16 αντικαθιστώντας intγιαushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

Όταν κοσκίνισμα του πρώτου 10000 πριμοδοτεί ένα τυπικό L1 cache του 32 θα υπάρξει υπέρβαση KiByte αλλά η λειτουργία εξακολουθεί να είναι πολύ γρήγορη (κλάσμα ενός χιλιοστού του δευτερολέπτου ακόμη και σε C #).

Εάν συγκρίνουμε αυτόν τον κώδικα στο κόσκινο deque τότε είναι εύκολο να δούμε ότι οι εργασίες της deque κόσκινο είναι πολύ πιο περίπλοκη, και δεν μπορεί να αποσβέσει αποτελεσματικά γενικά της, διότι κάνει πάντα τη συντομότερη δυνατή έκταση διαβάσεις-off σε μια σειρά (ακριβώς ένα ενιαίο διέλευσης off, μετά από παρακάμπτοντας όλα τα πολλαπλάσια που έχουν περάσει από ήδη).

Σημείωση: η C # κώδικα χρησιμοποιεί intαντί uintεπειδή νεότερα μεταγλωττιστές έχουν μια συνήθεια να παράγει υποβαθμισμένα κώδικας για uint, πιθανότατα με σκοπό να ωθήσει τους ανθρώπους προς υπέγραψε ακέραιοι ... Στην C ++ έκδοση του παραπάνω κώδικα θα χρησιμοποιηθεί unsignedπαντού, φυσικά? το σημείο αναφοράς έπρεπε να είναι σε C ++ γιατί ήθελα να βασίζεται σε μια δήθεν επαρκή τύπου deque ( std::deque<unsigned>? δεν υπήρχε κέρδος απόδοσης από τη χρήση unsigned short). Εδώ είναι οι αριθμοί για Haswell laptop μου (VC ++ 2015 / x64):

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

Σημείωση: οι χρόνοι C # είναι λίγο πολύ ακριβώς το διπλάσιο της C ++ χρόνους, το οποίο είναι πολύ καλό για C # και δείχνει ότι List<int>δεν είναι αδέξιος, ακόμη και αν κακοποιηθεί ως deque.

Το απλό κώδικα κόσκινο ακόμα φυσάει ο deque έξω από το νερό, αν και ήδη λειτουργεί πέρα ​​από την κανονική περιοχή εργασίας (L1 μέγεθος της μνήμης cache υπέρβαση κατά 50%, με συνοδό αλώνισμα μνήμη cache) του. Το κυριαρχεί μέρος εδώ είναι η ανάγνωση των κοσκινισμένο πρώτων αριθμών, και αυτό δεν επηρεάζεται πολύ από το πρόβλημα μνήμης cache. Σε κάθε περίπτωση η συνάρτηση έχει σχεδιαστεί για το κοσκίνισμα των παραγόντων των παραγόντων, δηλαδή το επίπεδο 0 σε μια ιεραρχία κόσκινο 3-επίπεδο, και τυπικά έχει να επιστρέψει μόνο μερικές εκατοντάδες παράγοντες ή ένα μικρό αριθμό των χιλιάδων. Εξ ου και η απλότητά της.

Απόδοση θα μπορούσε να βελτιωθεί κατά περισσότερο από μία τάξη μεγέθους με τη χρήση ενός τμηματικό κόσκινο και τη βελτιστοποίηση του κώδικα για την εξαγωγή των κοσκινισμένου πρώτους αριθμούς (ενταθεί mod 3 και ξετυλίγεται δύο φορές, ή mod 15 και ξετυλίγεται μία φορά), και κατά ακόμη μεγαλύτερη απόδοση θα μπορούσε να αποβληθούν από ο κώδικας με τη χρήση ενός mod 16 ή mod 30 του τροχού με όλες τις γαρνιτούρες (δηλαδή πλήρες ξετύλιγμα για όλα τα υπολείμματα). Κάτι τέτοιο εξηγείται στην απάντησή μου για να βρείτε προνομιακή τοποθετημένα πρώτος αριθμός πάνω σε αναθεώρηση κώδικα, όπου ένα παρόμοιο πρόβλημα συζητήθηκε. Αλλά είναι δύσκολο να δούμε το σημείο στη βελτίωση φορές υπο-χιλιοστό του δευτερολέπτου για ένα one-off έργο ...

Για να βάλουμε τα πράγματα λίγο σε μια προοπτική, εδώ είναι χρονισμούς της C ++ για κοσκίνισμα έως 100.000.000:

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

Αντίθετα, μια κατακερματισμένη κόσκινο σε C # με μερικές καμπάνες και σφυρίχτρες κάνει την ίδια δουλειά σε 95 ms (δεν υπάρχουν διαθέσιμες C ++ χρόνους, αφού κάνω κωδικό αμφισβητεί μόνο σε C # αυτή τη στιγμή).

Τα πράγματα μπορεί να φαίνονται σαφώς διαφορετική σε μια ερμηνευμένη γλώσσα όπως Python όπου κάθε λειτουργία έχει ένα βαρύ κόστος και η εναέρια διερμηνέας νάνοι όλες τις διαφορές οφείλονται σε προβλεπόμενη έναντι προβλέφθηκε λάθος κλαδιά ή την OPS υπο-κύκλου (shift, προσθήκη) vs. OPS πολλαπλών κύκλων (πολλαπλασιασμός , και ίσως ακόμη και διαίρεση). Αυτό είναι βέβαιο ότι θα διαβρώσει το πλεονέκτημα της απλότητας του Κόσκινο του Ερατοσθένη, και αυτό θα μπορούσε να κάνει το deque λύση λίγο πιο ελκυστικό.

Επίσης, πολλοί από τους χρόνους που αναφέρθηκαν από άλλους ερωτηθέντες σε αυτό το θέμα είναι κατά πάσα πιθανότητα κυριαρχείται από το χρόνο εξόδου . Αυτό είναι ένα εντελώς διαφορετικό πόλεμο, όπου κύριο όπλο μου είναι ένα απλό κατηγορίας, όπως αυτό:

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

Αυτό διαρκεί λιγότερο από 1 ms για τη σύνταξη 10000 (ταξινόμηση) αριθμούς. Είναι ένα στατικό τάξη, επειδή πρόκειται για έγγραφες ένταξη στην κωδικοποίηση υποβολές πρόκληση, με ελάχιστο κόπο και μηδενική επιβάρυνση.

Σε γενικές γραμμές το βρήκα να είναι πολύ πιο γρήγορα αν επικεντρώθηκε το έργο γίνεται σε ολόκληρη την παρτίδα, πράγμα που σημαίνει κόσκινο ένα συγκεκριμένο εύρος, στη συνέχεια, εξάγει όλα primes σε φορέα / πίνακα, τότε έκρηξη έξω όλη τη σειρά, στη συνέχεια κοσκινίζεται την επόμενη σειρά και ούτω καθεξής, αντί για το ανακάτεμα τα πάντα μαζί. Έχοντας ξεχωριστές λειτουργίες επικεντρώνεται σε συγκεκριμένα καθήκοντα που καθιστά ευκολότερο να αναμίξετε και να ταιριάξετε, επιτρέπει την επαναχρησιμοποίηση, και διευκολύνει την ανάπτυξη / δοκιμή.

Απαντήθηκε 19/04/2016 στις 17:07
πηγή χρήστη

ψήφοι
2

Στην Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Απαντήθηκε 22/02/2010 στις 08:45
πηγή χρήστη

ψήφοι
2

Το κόσκινο φαίνεται να είναι η λάθος απάντηση. Το κόσκινο σας δίνει τις πρώτους μέχρι έναν αριθμό Ν , όχι τα πρώτα Ν πρώτων αριθμών. Εκτέλεση @Imran ή @Andrew Szeto, και μπορείτε να πάρετε τις πρώτους μέχρι Ν

Το κόσκινο μπορεί να εξακολουθεί να μπορούν να χρησιμοποιηθούν, αν συνεχίσουμε να προσπαθούμε κόσκινα για όλο και μεγαλύτερους αριθμούς μέχρι να χτυπήσει ένα ορισμένο μέγεθος σύνολο των αποτελεσμάτων σας, και να χρησιμοποιήσετε κάποια προσωρινή αποθήκευση των αριθμών που έχουν ήδη ληφθεί, αλλά πιστεύω ότι θα εξακολουθεί να μην υπάρχει πιο γρήγορα να είναι από μια λύση, όπως @ Πέτρου .

Απαντήθηκε 19/06/2009 στις 19:12
πηγή χρήστη

ψήφοι
2

Προσαρμογή και σε συνέχεια της από GateKiller , εδώ είναι η τελική έκδοση που έχω χρησιμοποιήσει.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

Είναι βασικά η ίδια, αλλά έχω προσθέσει την πρόταση «σπάνε Sqrt» και να αλλάξει κάποια από τις μεταβλητές γύρω για να το κάνει να ταιριάζει καλύτερα για μένα. (Ήμουν εργάζονται για Euler και χρειάζεται την 10001th προνομιακή)

Απαντήθηκε 16/02/2009 στις 06:17
πηγή χρήστη

ψήφοι
1

Χρησιμοποιώντας Κόσκινο του Ερατοσθένη, υπολογισμός είναι αρκετά πιο γρήγορα σε σύγκριση με «γνωστή σε όλη την» αλγορίθμου πρώτων αριθμών.

Με τη χρήση ψευδοκώδικα από αυτό είναι wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), είμαι σε θέση να έχουν τη λύση για την C #.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes (100000000) παίρνει 2s και 330ms.

ΣΗΜΕΙΩΣΗ : Η τιμή μπορεί να ποικίλλει εξαρτάται από το υλικό Προδιαγραφές.

Απαντήθηκε 12/05/2016 στις 03:40
πηγή χρήστη

ψήφοι
1

Εδώ είναι μια λύση C ++, χρησιμοποιώντας μια μορφή SOE:

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

Σημειώστε ότι αυτή η έκδοση του Κόσκινο μπορεί να υπολογίσει πρώτους επ 'αόριστον.

Επίσης, σημειώστε ότι το STL dequeχρειάζεται O(1)χρόνο για να εκτελέσει push_back, pop_frontκαι τυχαίας προσπέλασης όμως subscripting.

Η resizeλειτουργία παίρνει O(n)χρόνο, όπου nείναι ο αριθμός των στοιχείων που προστίθενται. Λόγω πώς χρησιμοποιούμε αυτή τη λειτουργία, μπορούμε να θεωρήσουμε αυτό είναι μια μικρή σταθερή.

Το σώμα του whileστο βρόχο my_insertεκτελείται O(log log n)φορές, όπου nισούται με το μεταβλητό maybe_prime. Αυτό οφείλεται στο γεγονός ότι η έκφραση κατάσταση του whileθα αξιολογήσει την πραγματική μία φορά για κάθε πρώτο παράγοντα maybe_prime. Ανατρέξτε στην ενότητα « Λειτουργία Divisor » στη Wikipedia.

Ο πολλαπλασιασμός με τον αριθμό των φορών που my_insertλέγεται, δείχνει ότι θα πρέπει να πάρει O(n log log n)χρόνο στη λίστα nπρώτων αριθμών ... η οποία είναι, όπως ήταν αναμενόμενο, η χρονική πολυπλοκότητα που υποτίθεται ότι το κόσκινο του Ερατοσθένη για να έχουν.

Ωστόσο, αν και αυτός ο κώδικας είναι αποτελεσματική, δεν είναι η πιο αποτελεσματική ... Θα πρότεινα ανεπιφύλακτα τη χρήση εξειδικευμένη βιβλιοθήκη για την παραγωγή πρώτων αριθμών, όπως primesieve . Κάθε πραγματικά αποτελεσματική, καλά βελτιστοποιημένη λύση, θα διαρκέσει περισσότερο κώδικα από οποιονδήποτε θέλει να πληκτρολογήσετε σε Stackoverflow.

Απαντήθηκε 16/04/2016 στις 18:33
πηγή χρήστη

ψήφοι
1

Ο ακόλουθος κώδικας Mathcad υπολογίζονται τα πρώτα εκατομμύρια PRIMES σε λιγότερο από 3 λεπτά.

Να θυμίσουμε ότι αυτό θα πρέπει να χρησιμοποιούν κινητής υποδιαστολής διπλασιάζεται για όλους τους αριθμούς και τα βασικά ερμηνεύεται. Ελπίζω ότι η σύνταξη είναι σαφής.

εισάγετε περιγραφή της εικόνας εδώ

Απαντήθηκε 02/03/2014 στις 02:15
πηγή χρήστη

ψήφοι
1

Εδώ είναι ο κωδικός μου VB 2008, η οποία βρίσκει όλα primes <10.000.000 σε 1 λεπτό 27 δευτερόλεπτα για το laptop δουλειά μου. Είναι παραλείπει ακόμα και αριθμούς και αναζητά μόνο για πρώτους που είναι <η sqrt του αριθμού δοκιμών. Έχει σχεδιαστεί μόνο για να βρουν πρώτοι από 0 έως ένα Sentinal αξίας.

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
Απαντήθηκε 11/03/2011 στις 03:25
πηγή χρήστη

ψήφοι
0

Από θέλετε πρώτο 10000 primes μόνο, και όχι κωδικοποίησης σύνθετο αλγόριθμο εγώ θα προτείνω την ακόλουθη

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

τώρα κλήση είναι προνομιακή, όπως το χρειάζεστε

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Απαντήθηκε 16/11/2018 στις 05:34
πηγή χρήστη

ψήφοι
0

Μπορώ να σας δώσω κάποιες συμβουλές, θα πρέπει να την εφαρμόσουν.

  1. Για κάθε αριθμό, να πάρει το μισό αυτού του αριθμού. Π.χ. για τον έλεγχο 21, ληφθεί μόνο το υπόλοιπο διαιρώντας το από εύρος 2-10.
  2. Εάν του ένας μονός αριθμός, μόνο διαίρεση με μονό αριθμό, και το αντίστροφο. Όπως για 21, διαιρούν με 3, 5, 7, 9 μόνο.

Πιο αποτελεσματική μέθοδος πήρα μέχρι τώρα.

Απαντήθηκε 29/07/2018 στις 19:25
πηγή χρήστη

ψήφοι
0

Χρησιμοποιώντας τη μέθοδο Array.prototype.find () σε Javascript. 2214.486 ms

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms
Απαντήθηκε 09/06/2018 στις 21:49
πηγή χρήστη

ψήφοι
0

Εδώ ο κώδικας που έκανα:


enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}
Απαντήθηκε 20/01/2018 στις 15:50
πηγή χρήστη

ψήφοι
0

Εδώ είναι ο κωδικός μου που βρίσκει πρώτα 10.000 πρώτοι σε 0.049655 sec για το laptop μου, πρώτα 1.000.000 πρώτων αριθμών σε λιγότερο από 6 δευτερόλεπτα και η πρώτη 2.000.000 σε 15 δευτερόλεπτα
Μια μικρή εξήγηση. Αυτή η μέθοδος χρησιμοποιεί 2 τεχνικές για να βρει πρώτος αριθμός

  1. καταρχάς οποιοδήποτε μη-πρώτος αριθμός είναι ένα σύνθετο από πολλαπλάσια των πρώτων αριθμών, έτσι αυτή η δοκιμή κώδικα διαιρώντας τον αριθμό δοκιμής από μικρότερους πρώτους αριθμούς αντί για οποιοδήποτε αριθμό, αυτό μειώνει υπολογισμός από atleast 10 φορές για ένα 4 ψήφιο αριθμό και ακόμη περισσότερο για ένα μεγαλύτερο αριθμό
  2. δεύτερον, εκτός από τη διαίρεση του Πρωθυπουργού, το χωρίζει μόνο από τους πρώτους αριθμούς που είναι μικρότερη ή ίση με τη ρίζα του αριθμού που εξετάζεται περαιτέρω μείωση των υπολογισμών σε μεγάλο βαθμό, αυτό λειτουργεί γιατί οποιοσδήποτε αριθμός που είναι μεγαλύτερος από ό, τι ρίζα του αριθμού θα έχει μια σειρά ομόλογό που πρέπει να είναι μικρότερη από ό, τι ρίζα του αριθμού, αλλά από τη στιγμή που έχουν δοκιμαστεί σε όλους τους αριθμούς μικρότερη από τη ρίζα ήδη, γι 'αυτό δεν χρειάζεται να ασχοληθείτε με αριθμό μεγαλύτερο από τη ρίζα του αριθμού που δοκιμάζεται.

Δείγμα εξόδου για πρώτη 10,000 πρώτος αριθμός
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Εδώ είναι ο κώδικας σε γλώσσα C, Πληκτρολογήστε 1 και, στη συνέχεια, 10.000 για να εκτυπώσετε τα πρώτα 10.000 πρώτους.
Επεξεργασία: Ξέχασα αυτή περιέχει η βιβλιοθήκη math, αν είστε σε παράθυρα ή το Visual Studio από αυτή που θα έπρεπε να είναι ωραία, αλλά σε linux θα πρέπει να καταρτίσει τον κώδικα χρησιμοποιώντας -lm επιχείρημα ή ο κωδικός ενδέχεται να μην λειτουργούν
Παράδειγμα: gcc -o -Wall «% e " "% f" -lm

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}
Απαντήθηκε 06/05/2017 στις 11:48
πηγή χρήστη

ψήφοι
0

Έχω ήδη εργάζονται σε primes εύρημα για περίπου ένα χρόνο. Αυτό είναι ό, τι βρήκα να είναι η ταχύτερα:

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

1902465190909 νανο δευτερόλεπτα για να φτάσετε στο 2147483629 ξεκινώντας από το 2.

Απαντήθηκε 14/08/2016 στις 00:20
πηγή χρήστη

ψήφοι
0

Θα περάσετε κάποιο χρόνο για να γράψω ένα πρόγραμμα υπολογισμού πολλή των πρώτων αριθμών και αυτό είναι ο κωδικός έχω συνηθίσει να υπολογίσει ένα αρχείο κειμένου που περιέχει τα πρώτα 1.000.000.000 πρώτους. Είναι στα γερμανικά, αλλά το ενδιαφέρον είναι η μέθοδος calcPrimes(). Οι πρώτοι αριθμοί αποθηκεύονται σε έναν πίνακα που ονομάζεται Primzahlen. Θα ήθελα να συστήσω ένα επεξεργαστή 64bit, επειδή οι υπολογισμοί είναι με ακέραιοι 64bit.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}
Απαντήθηκε 23/04/2012 στις 20:46
πηγή χρήστη

ψήφοι
0

Έχω γράψει αυτό το χρησιμοποιούν python, όπως μόλις άρχισε να μαθαίνει αυτό, και λειτουργεί απολύτως εντάξει. Η προνομιακή 10,000th παράγουν από αυτό τον κωδικό, όπως αυτά που αναφέρονται στο http://primes.utm.edu/lists/small/10000.txt . Για να ελέγξετε αν nείναι πρώτος ή όχι, χάσμα nμε τους αριθμούς από το 2να sqrt(n). Εάν οποιαδήποτε από αυτό το εύρος του αριθμού χωρίζει τέλεια nτότε δεν είναι προνομιακή.

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))
Απαντήθηκε 27/12/2010 στις 18:37
πηγή χρήστη

ψήφοι
-1
using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}
Απαντήθηκε 08/05/2012 στις 05:15
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more