Algoritmo veloce per trovare i numeri primi?

Question

Prima di tutto - Ho controllato molto in questo forum e non ho trovato qualcosa abbastanza veloce. Cerco di creare una funzione che restituisca i numeri primi in un intervallo specificato. Per esempio ho fatto questa funzione (in C#) usando il setaccio di Eratostene. Ho provato anche setaccio Atkin ma quella Eratostene corre più veloce (nel mio implementazione):

public static void SetPrimesSieve(int Range) 
    { 
     Primes = new List<uint>(); 
     Primes.Add(2); 
     int Half = (Range - 1) >> 1; 
     BitArray Nums = new BitArray(Half, false); 
     int Sqrt = (int)Math.Sqrt(Range); 
     for (int i = 3, j; i <= Sqrt;) 
     { 
      for (j = ((i * i) >> 1) - 1; j < Half; j += i) 
       Nums[j] = true; 
      do 
       i += 2; 
      while (i <= Sqrt && Nums[(i >> 1) - 1]); 
     } 
     for (int i = 0; i < Half; ++i) 
      if (!Nums[i]) 
       Primes.Add((uint)(i << 1) + 3); 
    } 

Si corre circa due volte più veloce di codici & algoritmi che ho trovato ... C'è dovrebbe essere un modo più veloce per trovare i numeri primi, potresti aiutarmi?

Answer 1

Durante la ricerca di algoritmi su questo argomento (per il progetto Eulero) non ricordo di aver trovato nulla più veloce. Se la velocità è davvero la preoccupazione, hai pensato di archiviare i numeri primi in modo tale che devi semplicemente cercarli?

MODIFICA: ricerca rapida su google trovata this, confermando che il metodo più veloce sarebbe solo per visualizzare i risultati e cercarli secondo le necessità.

Un'altra modifica: è possibile trovare ulteriori informazioni here, essenzialmente un duplicato di questo argomento. Il primo post afferma che il setaccio di atkin è stato più veloce di quanto non lo fosse al momento della generazione al volo.

Answer 2

Diversi commenti.

1. Per la velocità, pre-calcolare quindi caricare dal disco. È super veloce. L'ho fatto in Java molto tempo fa.

2. Non archiviare come array, archiviare come bitrdenza per numeri dispari. Più efficiente sulla memoria

3. Se la tua domanda di velocità è che vuoi che questo particolare calcolo funzioni velocemente (devi giustificare il motivo per cui non puoi precomputerlo e caricarlo dal disco) devi codificare un setaccio migliore di Atkin. È più veloce Ma solo leggermente.

4. Non è stato indicato l'utilizzo finale di questi numeri primi. Potremmo perdere qualcosa completamente perché non ci hai detto l'applicazione. Diteci uno schizzo dell'applicazione e le risposte saranno mirate meglio per il vostro contesto.

5. Perché mai pensi che esista qualcosa di più veloce? Non hai giustificato la tua impressione. Questo è un problema molto difficile. (Che è quello di trovare qualcosa di più veloce)

Answer 3

Si può fare di meglio con il Sieve of Atkin, ma è abbastanza difficile da implementare in fretta e correttamente. Una semplice traduzione dello pseudo-codice di Wikipedia probabilmente non è abbastanza buona.

Answer 4

L'algoritmo più veloce nella mia esperienza finora è il setaccio di Erathostenes con fattorizzazione della ruota per 2, 3 e 5, in cui i numeri primi tra i numeri rimanenti sono rappresentati come bit in una matrice di byte. In Java su un nucleo del mio computer portatile di 3 anni ci vogliono 23 secondi per calcolare i numeri primi fino a 1 miliardo.

Con la scomposiz- zazione delle ruote, il setaccio di Atkin era circa un fattore due più lento, mentre con un ordinario BitSet era circa il 30% più veloce.

Vedere anche this answer.

Answer 5

Ho fatto un algoritmo in grado di trovare numeri primi nell'intervallo 2-90.000.000 per 0.65 sec su I 350M-notebook, scritto in C .... devi usare operazioni bit a bit e avere "codice" per ricalcolare l'indice del tuo array per indicizzare il bit concreto che desideri. per esempio Se vuoi le pieghe del numero 2, i bit concreti saranno ad esempio .... 10101000 ... quindi se leggi da sinistra ... ottieni indice 4,6,8 ... questo è