performance - trovare - tabella numeri primi pdf




Il codice più efficiente per i primi 10000 numeri primi? (20)

@Matt: log (log (10000)) è ~ 2

Dall'articolo di Wikipedia (che hai citato) Sieve of Atkin :

Questo setaccio calcola i numeri primi fino a N utilizzando le operazioni O(N/log log N) con solo N 1/2 + o (1) bit di memoria. È un po 'meglio del setaccio di Eratostene che utilizza operazioni O(N) e bit di memoria O (N 1/2 (log log N) / log N) (AOL Atkin, DJ Bernstein, 2004) . Queste complessità computazionali asintotiche includono semplici ottimizzazioni, come la fattorizzazione delle ruote e la suddivisione del calcolo in blocchi più piccoli.

Date le complessità computazionali asintotiche lungo O(N) (per Eratostene) e O(N/log(log(N))) (per Atkin) non possiamo dire (per la piccola N=10_000 ) quale algoritmo se implementato sarà più veloce.

Achim Flammenkamp ha scritto in Il setaccio di Eratostene :

citato da:

@ num1

Per intervalli superiori a circa 10 ^ 9, sicuramente per quelli> 10 ^ 10, il setaccio di Eratostene è sovraperformato dal setaccio di Atkins e Bernstein che utilizza irriducibili forme quadratiche binarie. Vedi il loro documento per informazioni di base così come il paragrafo 5 del Ph.D. di W. Galway. tesi.

Pertanto per 10_000 setaccio di Eratostene può essere più veloce del setaccio di Atkin.

Per rispondere a OP il codice è prime_sieve.c (citato da num1 )

Voglio stampare i primi 10000 numeri primi. Qualcuno può darmi il codice più efficiente per questo? chiarimenti:

  1. Non importa se il codice è inefficiente per n> 10000.
  2. La dimensione del codice non ha importanza.
  3. Non puoi semplicemente codificare i valori in alcun modo.

Adattandosi e seguendo da GateKiller , ecco la versione finale che ho usato.

    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;
    }

È praticamente lo stesso, ma ho aggiunto il suggerimento "break on Sqrt" e ho cambiato alcune delle variabili in giro per adattarmi meglio a me. (Stavo lavorando su Euler e avevo bisogno del 10001esimo numero primo)


Ecco il mio codice VB 2008, che trova tutti i numeri primi <10.000.000 in 1 minuto e 27 secondi sul mio laptop di lavoro. Salta i numeri pari e cerca solo numeri primi <sqrt del numero di test. È progettato solo per trovare numeri primi da 0 a un valore sentinale.

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

Ecco un setaccio di Eratostene che ho scritto in PowerShell qualche giorno fa. Ha un parametro per identificare il numero di numeri primi che dovrebbero essere restituiti.

#
# 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
}

Ho adattato il codice trovato su CodeProject per creare quanto segue:

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 + " ");
    }
}

Il test sul mio server ASP.NET ha richiesto il rountine circa 1 minuto per l'esecuzione.


Il seguente codice Mathcad ha calcolato il primo milione di numeri primi in meno di 3 minuti.

Tieni presente che questo sarebbe utilizzare doppie in virgola mobile per tutti i numeri e viene sostanzialmente interpretato. Spero che la sintassi sia chiara.


In Haskell, possiamo scrivere quasi parola per parola la definizione matematica del setaccio di Eratostene, "i numeri primi sono numeri naturali al di sopra di 1 senza alcun numero composto, dove i composti si trovano per enumerazione dei multipli di ciascun primo ":

import Data.List.Ordered (minus, union)

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

primes !! 10000 primes !! 10000 è quasi istantaneo.

Riferimenti:

Il codice sopra è facilmente ottimizzato per lavorare solo sulle probabilità, primes = 2 : 3 : minus [5,7..] (foldr (\pr -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)) . La complessità temporale è molto migliorata (fino a quasi un fattore log superiore all'ottimale) piegando in una struttura ad albero, e la complessità spaziale è drasticamente migliorata dalla produzione di primer a più stadi , in

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

(In Haskell le parentesi sono utilizzate per il raggruppamento, una chiamata di funzione è indicata solo dalla giustapposizione, (:) è un operatore di contro per gli elenchi e (.) È un operatore di composizione funzionale: (f . g) x = (\y -> f (gy)) x = f (gx) ).


In Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 

Non è affatto efficiente, ma è possibile utilizzare un'espressione regolare per verificare i numeri primi.

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

Questo verifica se, per una stringa composta da k1 ” s, k non è un numero primo (ovvero se la stringa è costituita da un “ 1 ” o da un numero qualsiasi di “ 1 ” che può essere espresso come prodotto n -ary).


Questo non è strettamente contro la limitazione dell'hardcoding, ma si avvicina terribilmente. Perché non scaricare programmaticamente questo elenco e stamparlo, invece?

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


GateKiller , che ne dici di aggiungere una break a questo if nel ciclo foreach ? Questo accelererebbe molto le cose perché se come 6 è divisibile per 2 non è necessario verificare con 3 e 5. (Vorrei comunque votare la tua soluzione se avessi abbastanza reputazione :-) ...)

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 + " ");
    }
}

Il setaccio di Atkin è probabilmente quello che stai cercando, il suo tempo di esecuzione limite superiore è O (N / log log N).

Se esegui solo i numeri 1 in più e 1 in meno rispetto ai multipli di 6, potrebbe essere ancora più veloce, poiché tutti i numeri primi sopra 3 sono 1 di distanza da un multiplo di sei. Risorsa per la mia affermazione


Dato che vuoi solo i primi 10000 numeri primi, piuttosto che codificare un algoritmo complesso suggerirò quanto segue

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;
}

ora la chiamata è ottima di cui hai bisogno

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}

Ecco il codice che ho creato:

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;
}

Questa è una vecchia domanda, ma qui c'è qualcosa che manca a tutti ...

Per i primi questa piccola divisione di prova non è così lenta ... ci sono solo 25 numeri primi sotto i 100. Con così pochi numeri primi da testare e numeri così piccoli, possiamo fare un bel trucco!

Se a è coprime a b, gcd ab = 1. Coprime. Parola divertente Significa che non condivide alcun fattore primo . Possiamo così verificare la divisibilità per diversi numeri primi con una chiamata GCD. Quanti? Bene, il prodotto dei primi 15 numeri primi è inferiore a 2 ^ 64. E il prodotto dei prossimi 10 è anche inferiore a 2 ^ 64. Ecco tutti i 25 di cui abbiamo bisogno. Ma ne vale la pena?

Vediamo:

check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes

a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes

Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)

Un miglioramento di 6 volte lì.

( lengthè per forzare il calcolo dell'elenco. Per impostazione predefinita, Haskell stampa cose 1 carattere Unicode alla volta e quindi effettivamente la stampa dell'elenco dominerà il tempo o dominerà la quantità di codice effettivo utilizzato.)

Ovviamente, questo è in esecuzione in GHCi - un sostituto in esecuzione di codice interpretato - su un vecchio laptop e non sta interpretando nessuno di questi numeri come int64s o addirittura BigInts, né lo farà anche se lo chiedi a (beh, puoi forzarlo , ma è brutto e non aiuta davvero). Interpreta ogni singolo numero lì come cose generalizzate simili a Integer che possono essere specializzate in un tipo particolare tramite la ricerca nel dizionario, e sta attraversando un elenco collegato (che non è fuso qui perché non è compilato) 3 volte. È interessante notare che la fusione manuale dei due filtri in realtà lo rallenta nel REPL.

Compiliamolo:

...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total   time    0.000s  (  0.004s elapsed)

Utilizzando il rapporto RTS perché Windows. Alcune linee tagliate perché non rilevanti - erano altri dati GC o misurazioni di solo una parte dell'esecuzione e insieme sommano fino a 0,004 s (o meno). Inoltre, non è una piega costante, perché Haskell in realtà non fa molto. Se pieghiamo costantemente noi stessi ( main = print 10000), otteniamo un'allocazione notevolmente inferiore:

...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total   time    0.000s  (  0.001s elapsed)

Letteralmente quanto basta per caricare il runtime, quindi scoprire che non c'è altro da fare che stampare un numero ed uscire. Aggiungiamo la fattorizzazione delle ruote:

wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel

Total   time    0.000s  (  0.003s elapsed)

Riduci circa 1/3 rispetto al nostro riferimento di main = print 10000, ma c'è sicuramente spazio per una maggiore ottimizzazione. Ad esempio, ha effettivamente smesso di eseguire un GC, mentre con le modifiche non dovrebbe esserci alcun uso dell'heap. Per qualche motivo, la compilazione per la profilazione qui in realtà riduce il tempo di esecuzione a 2 millisecondi:

Tue Nov 12 21:13 2019 Time and Allocation Profiling Report  (Final)

   Primes.exe +RTS -p -RTS

total time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)
total alloc =     967,120 bytes  (excludes profiling overheads)

Lo lascerò com'è per ora, sono abbastanza sicuro che il jitter casuale stia iniziando a dominare.


Usando Sieve of Eratosthenes, il calcolo è molto più veloce rispetto all'algoritmo di numeri primi "a livello noto".

Usando lo pseudocodice dal suo wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), posso avere la soluzione su 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) richiede 2 secondi e 330 ms.

NOTA : il valore può variare in base alle specifiche hardware.


Ho scritto questo usando Python, appena ho iniziato a impararlo, e funziona perfettamente. Il 10.000esimo primo generato da questo codice è lo stesso menzionato in http://primes.utm.edu/lists/small/10000.txt . Per verificare se nè primo o no, dividi nper i numeri da 2a sqrt(n). Se uno di questi intervalli di numeri si divide perfettamente n, non è un numero primo.

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

Lavoro a trovare numeri primi da circa un anno. Questo è quello che ho scoperto essere il più veloce:

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 nano secondi per arrivare a 2147483629 a partire da 2.


Utilizzo del metodo Array.prototype.find () in 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

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();
        }
    }
}




primes