Divertimento con il calcolo dei numeri primi
https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ci stiamo divertendo un po' qui al lavoro.Tutto è iniziato con uno dei ragazzi che ha configurato un Hackintosh e ci chiedevamo se fosse più veloce di un Windows Box con (quasi) le stesse specifiche che abbiamo noi.Quindi abbiamo deciso di scrivere un piccolo test.Solo un semplice calcolatore di numeri primi.È scritto in Java e ci dice il tempo necessario per calcolare i primi n numeri primi.
Versione ottimizzata di seguito: ora richiede circa 6,6 secondi
public class Primes {
public static void main(String[] args) {
int topPrime = 150000;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
}
Abbiamo praticamente perso la trama dell'intera faccenda Hackintosh vs PC e ci stiamo solo divertendo un po' con l'ottimizzazione.Il primo tentativo senza ottimizzazioni (il codice sopra ne ha un paio) è durato circa 52,6 minuti per trovare i primi 150000 numeri primi.Questa ottimizzazione dura circa 47,2 minuti.
Se vuoi provare a pubblicare i tuoi risultati, attaccali.
Le specifiche per il PC su cui lo utilizzo sono Pentium D 2,8 GHz, 2 GB di RAM, con Ubuntu 8.04.
La migliore ottimizzazione finora è stata la radice quadrata dell'attuale, menzionata per la prima volta da Jason Z.
Soluzione
Bene, vedo un paio di rapide ottimizzazioni che possono essere fatte. Per prima cosa non devi provare ogni numero fino alla metà del numero corrente.
Invece devi solo provare fino alla radice quadrata del numero corrente.
E l'altra ottimizzazione è stata ciò che BP ha detto con una svolta: Invece di
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
utilizzo
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
Questo dovrebbe accelerare parecchio.
Modifica
Ulteriori ottimizzazioni per gentile concessione di Joe Pineda:
Rimuovi la variabile & Quot; top & Quot ;.
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
Se questa ottimizzazione aumenta davvero la velocità dipende da Java.
Il calcolo della radice quadrata richiede molto tempo rispetto alla moltiplicazione di due numeri. Tuttavia, poiché spostiamo la moltiplicazione nel ciclo for, questo viene fatto ogni singolo ciclo. Quindi questo POTREBBE rallentare le cose a seconda di quanto è veloce l'algoritmo radice quadrata in Java.
Altri suggerimenti
Questo è un po 'peggio di quanto il mio setaccio abbia fatto su un 888 Mhz 8088 in turbo pascal nel 1986 o giù di lì. Ma questo dopo ottimizzazioni :)
Dato che li stai cercando in ordine crescente, puoi tenere un elenco dei numeri primi che hai già trovato e controllare solo la divisibilità nei loro confronti, poiché tutti i numeri non primi possono essere ridotti a un elenco di numeri primi inferiori fattori. Combina questo con il suggerimento precedente di non controllare i fattori sulla radice quadrata del numero corrente e avrai un'implementazione davvero dannatamente efficiente.
Ecco una soluzione semplice e veloce:
- Trovare numeri primi inferiori a 100000; 9592 trovati in 5 ms
- Trovare numeri primi inferiori a 1000000; 78498 trovati in 20 ms
- Trovare numeri primi inferiori a 10000000; 664579 trovati in 143 ms
- Trovare numeri primi inferiori a 100000000; 5761455 sono stati trovati nel 2024 ms
-
Trovare numeri primi inferiori a 1000000000; 50847534 trovati in 23839 ms
//returns number of primes less than n private static int getNumberOfPrimes(final int n) { if(n < 2) return 0; BitSet candidates = new BitSet(n - 1); candidates.set(0, false); candidates.set(1, false); candidates.set(2, n); for(int i = 2; i < n; i++) if(candidates.get(i)) for(int j = i + i; j < n; j += i) if(candidates.get(j) && j % i == 0) candidates.set(j, false); return candidates.cardinality(); }
Ci serve meno di un secondo (2,4 GHz) per generare i primi 150000 numeri primi in Python usando Sieve of Eratosthenes:
#!/usr/bin/env python
def iprimes_upto(limit):
"""Generate all prime numbers less then limit.
http://stackoverflow.com/questions/188425/project-euler-problem#193605
"""
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n
for i in range(n*n, limit, n): # start at ``n`` squared
is_prime[i] = False
def sup_prime(n):
"""Return an integer upper bound for p(n).
p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)
where p(n) is the n-th prime.
http://primes.utm.edu/howmany.shtml#2
"""
from math import ceil, log
assert n >= 13
pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
return int(ceil(pn))
if __name__ == '__main__':
import sys
max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
print("Generated %d primes" % len(primes))
n = 100
print("The first %d primes are %s" % (n, primes[:n]))
Esempio:
$ python primes.py
Generated 153465 primes
The first 100 primes are [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, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541]
In C #:
class Program
{
static void Main(string[] args)
{
int count = 0;
int max = 150000;
int i = 2;
DateTime start = DateTime.Now;
while (count < max)
{
if (IsPrime(i))
{
count++;
}
i++;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
if (n < 4)
return true;
if (n % 2 == 0)
return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}
Output:
Tempo totale impiegato: 2,087 secondi
Tenendo presente che esistono modi migliori per cercare numeri primi ...
Penso che puoi fare questo ciclo:
for (int i = 2; i < top; i++)
e rendilo tale che la tua variabile counter i passi da 3 e cerchi solo di fare la mod su numeri dispari, dal momento che tutti i numeri primi diversi da 2 non sono mai divisibili per nessun numero pari.
Fa la ri-dichiarazione della variabile prime
while (count < topPrime) {
boolean prime = true;
all'interno del ciclo lo rende inefficiente? (Suppongo che non abbia importanza, poiché penso che Java lo ottimizzerebbe)
boolean prime;
while (count < topPrime) {
prime = true;
C #
Miglioramento a Codice di Aistina :
Questo fa uso del fatto che tutti i numeri primi maggiori di 3 sono nella forma 6n + 1 o 6n - 1.
Si è trattato di un aumento della velocità del 4-5% rispetto all'incremento di 1 per ogni passaggio del ciclo.
class Program
{
static void Main(string[] args)
{
DateTime start = DateTime.Now;
int count = 2; //once 2 and 3
int i = 5;
while (count < 150000)
{
if (IsPrime(i))
{
count++;
}
i += 2;
if (IsPrime(i))
{
count++;
}
i += 4;
}
DateTime end = DateTime.Now;
Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
Console.ReadLine();
}
static bool IsPrime(int n)
{
//if (n < 4)
//return true;
//if (n % 2 == 0)
//return false;
int s = (int)Math.Sqrt(n);
for (int i = 2; i <= s; i++)
if (n % i == 0)
return false;
return true;
}
}
Il mio approccio all'ottimizzazione, evitando trucchi troppo enigmatici. Uso il trucco di I-GIVE-TERRIBLE-ADVICE, che ho conosciuto e dimenticato ... :-)
public class Primes
{
// Original code
public static void first()
{
int topPrime = 150003;
int current = 2;
int count = 0;
int lastPrime = 2;
long start = System.currentTimeMillis();
while (count < topPrime) {
boolean prime = true;
int top = (int)Math.sqrt(current) + 1;
for (int i = 2; i < top; i++) {
if (current % i == 0) {
prime = false;
break;
}
}
if (prime) {
count++;
lastPrime = current;
// System.out.print(lastPrime + " "); // Checking algo is correct...
}
if (current == 2) {
current++;
} else {
current = current + 2;
}
}
System.out.println("\n-- First");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
}
// My attempt
public static void second()
{
final int wantedPrimeNb = 150000;
int count = 0;
int currentNumber = 1;
int increment = 4;
int lastPrime = 0;
long start = System.currentTimeMillis();
NEXT_TESTING_NUMBER:
while (count < wantedPrimeNb)
{
currentNumber += increment;
increment = 6 - increment;
if (currentNumber % 2 == 0) // Even number
continue;
if (currentNumber % 3 == 0) // Multiple of three
continue;
int top = (int) Math.sqrt(currentNumber) + 1;
int testingNumber = 5;
int testIncrement = 2;
do
{
if (currentNumber % testingNumber == 0)
{
continue NEXT_TESTING_NUMBER;
}
testingNumber += testIncrement;
testIncrement = 6 - testIncrement;
} while (testingNumber < top);
// If we got there, we have a prime
count++;
lastPrime = currentNumber;
// System.out.print(lastPrime + " "); // Checking algo is correct...
}
System.out.println("\n-- Second");
System.out.println("Last prime = " + lastPrime);
System.out.println("Total time = " + (double) (System.currentTimeMillis() - start) / 1000);
}
public static void main(String[] args)
{
first();
second();
}
}
Sì, ho usato un etichettato continue, la prima volta che li provo in Java ...
So di saltare il calcolo dei primi pochi primi, ma sono ben noti, inutile ricalcolarli. :-) Posso codificare il loro output se necessario! Inoltre, non dà comunque un vantaggio decisivo.
Risultati:
- Primo
Ultimo numero primo = 2015201
Tempo totale = 4.281
- Seconda
Ultimo numero primo = 2015201
Tempo totale = 0,953
Non male. Potrei essere migliorato un po ', suppongo, ma troppa ottimizzazione può uccidere un buon codice.
Dovresti essere in grado di rendere il ciclo interno due volte più veloce valutando solo i numeri dispari. Non sono sicuro che si tratti di Java valido, sono abituato al C ++, ma sono sicuro che possa essere adattato.
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
Ho deciso di provarlo in Fa#, il mio primo tentativo decente.Usando il Setaccio di Eratostene sul mio Core 2 Duo da 2,2 Ghz ne vengono eseguiti 2..150.000 in circa 200 millisecondi.Ogni volta che si chiama se stesso, vengono eliminati i multipli correnti dall'elenco, quindi diventa semplicemente più veloce man mano che procede.Questo è uno dei miei primi tentativi in F#, quindi qualsiasi commento costruttivo sarebbe apprezzato.
let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
match sieve with
| [] -> sieve
| _ when sqrt(float(max)) < float sieve.[0] -> sieve
| _ -> let prime = sieve.[0]
let filtered = List.filter(fun x -> x % prime <> 0) sieve // Removes the prime as well so the recursion works correctly.
let result = getPrimes filtered max
prime::result // The filter removes the prime so add it back to the primes result.
let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds
Scommetto che Miller-Rabin sarebbe più veloce. Se provi abbastanza numeri contigui diventa deterministico, ma non mi preoccuperei nemmeno. Una volta che un algoritmo randomizzato raggiunge il punto in cui il suo tasso di fallimento è uguale alla probabilità che un singhiozzo della CPU causi un risultato errato, non ha più importanza.
Ecco la mia soluzione ... è abbastanza veloce ... calcola i numeri primi tra 1 e 10.000.000 in 3 secondi sulla mia macchina (core i7 @ 2.93Ghz) su Vista64.
La mia soluzione è in C, ma non sono un programmatore C professionista. Sentiti libero di criticare l'algoritmo e il codice stesso :)
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880
//list of calculated primes
__int64* primes;
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;
//Prints all of the calculated primes
void PrintPrimes()
{
__int64 i;
for(i=0; i<primeCount; i++)
{
printf("%d ", primes[i]);
}
}
//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
register __int64 i;
double square;
primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
primeCount = 0;
arraySize = ARRAYMULT;
//we provide the first prime because its even, and it would be convenient to start
//at an odd number so we can skip evens.
primes[0] = 2;
primeCount++;
for(i=3; i<max; i+=2)
{
int j;
square = sqrt((double)i);
//only test the current candidate against other primes.
for(j=0; j<primeCount; j++)
{
//prime divides evenly into candidate, so we have a non-prime
if(i%primes[j]==0)
break;
else
{
//if we've reached the point where the next prime is > than the square of the
//candidate, the candidate is a prime... so we can add it to the list
if(primes[j] > square)
{
//our array has run out of room, so we need to expand it
if(primeCount >= arraySize)
{
int k;
__int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));
for(k=0; k<primeCount; k++)
{
newArray[k] = primes[k];
}
arraySize += ARRAYMULT;
free(primes);
primes = newArray;
}
//add the prime to the list
primes[primeCount] = i;
primeCount++;
break;
}
}
}
}
}
int main()
{
int max;
time_t t1,t2;
double elapsedTime;
printf("Enter the max number to calculate primes for:\n");
scanf_s("%d",&max);
t1 = time(0);
CalcPrime(max);
t2 = time(0);
elapsedTime = difftime(t2, t1);
printf("%d Primes found.\n", primeCount);
printf("%f seconds elapsed.\n\n",elapsedTime);
//PrintPrimes();
scanf("%d");
return 1;
}
Ecco la mia opinione su di esso. Il programma è scritto in C e impiega 50 millisecondi sul mio laptop (Core 2 Duo, 1 GB di RAM). Sto mantenendo tutti i numeri primi calcolati in un array e provando la divisibilità solo fino a sqrt di numero. Naturalmente, questo non funziona quando abbiamo bisogno di un numero molto elevato di numeri primi (provato con 100000000) poiché l'array cresce troppo grande e dà un errore di seg.
/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000
main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;
primes[0] = 2;
count = 1;
for(i = 3; count < TOTALPRIMES; i+= 2){
isPrime = 1;
//check divisiblity only with previous primes
for(j = 0; j < count; j++){
cpr = primes[j];
if(i % cpr == 0){
isPrime = 0;
break;
}
if(cpr*cpr > i){
break;
}
}
if(isPrime == 1){
//printf("Prime: %d\n", i);
primes[count] = i;
count++;
}
}
printf("Last prime = %d\n", primes[TOTALPRIMES - 1]);
}
$ time ./a.out Last prime = 163841 real 0m0.045s user 0m0.040s sys 0m0.004s
@ Mark Ransom - non sono sicuro che si tratti di codice java
Si lamenteranno possibilmente ma ho voluto riscrivere usando il paradigma di cui ho imparato a fidarmi di Java e hanno detto di divertirsi un po ', per favore assicurati di capire che le specifiche non dicono nulla che effetti l'ordinamento sul restituito set di risultati, inoltre si lanciano i valori dei punti del set di risultati () in un tipo di elenco dato il mio unico nel Blocco note prima di prendere una breve commissione
=============== inizio codice non testato ===============
package demo;
import java.util.List;
import java.util.HashSet;
class Primality
{
int current = 0;
int minValue;
private static final HashSet<Integer> resultSet = new HashSet<Integer>();
final int increment = 2;
// An obvious optimization is to use some already known work as an internal
// constant table of some kind, reducing approaches to boundary conditions.
int[] alreadyKown =
{
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, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541
};
// Trivial constructor.
public Primality(int minValue)
{
this.minValue = minValue;
}
List calcPrimes( int startValue )
{
// eliminate several hundred already known primes
// by hardcoding the first few dozen - implemented
// from prior work by J.F. Sebastian
if( startValue > this.minValue )
{
// Duh.
current = Math.abs( start );
do
{
boolean prime = true;
int index = current;
do
{
if(current % index == 0)
{
// here, current cannot be prime so break.
prime = false;
break;
}
while( --index > 0x00000000 );
// Unreachable if not prime
// Here for clarity
if ( prime )
{
resultSet dot add ( or put or whatever it is )
new Integer ( current ) ;
}
}
while( ( current - increment ) > this.minValue );
// Sanity check
if resultSet dot size is greater that zero
{
for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
return resultSet;
}
else throw an exception ....
}
=============== fine codice non testato ===============
L'uso dei set di hash consente di cercare i risultati come alberi B, quindi i risultati potrebbero essere impilati fino a quando la macchina non inizia a guastarsi, quindi quel punto iniziale potrebbe essere utilizzato per un altro blocco di test == la fine di una corsa utilizzata come valore del costruttore per un'altra corsa, persistendo sul lavoro su disco già realizzato e consentendo progetti di feed-forward incrementali. Bruciato in questo momento, la logica del loop ha bisogno di analisi.
patch (più aggiungi sqrt):
if(current % 5 == 0 )
if(current % 7 == 0 )
if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}
// and - new work this morning:
package demo;
/**
*
* Buncha stuff deleted for posting .... duh.
*
* @author Author
* @version 0.2.1
*
* Note strings are base36
*/
public final class Alice extends java.util.HashSet<java.lang.String>
{
// prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
// using Java built-in on amd sempron 1.8 ghz / 1600 mhz front side bus 256 k L-2
public static void main(java.lang.String[] args)
{
try
{
final long start=System.currentTimeMillis();
// VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
final java.lang.Integer upperBound=new java.lang.Integer(40000);
int index = upperBound.intValue();
final java.util.HashSet<java.lang.String>hashSet
= new java.util.HashSet<java.lang.String>(upperBound.intValue());//
// Arbitraily chosen value, based on no idea where to start.
java.math.BigInteger probablePrime
= new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
do
{
java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
{
probablePrime = nextProbablePrime;
if( ( index % 100 ) == 0x00000000 )
{
// System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
continue;
}
else
{
continue;
}
}
else
{
throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
Integer.toString(upperBound.intValue() - index)));
}
}
while(--index > 0x00000000);
System.err.println(Long.toString( System.currentTimeMillis() - start));
}
catch(java.security.NoSuchAlgorithmException nsae)
{
// Never happen
return;
}
catch(java.lang.StackOverflowError soe)
{
// Might happen
System.out.println(soe.getMessage());//
return;
}
}
}// end class Alice
Ho trovato questo codice da qualche parte sulla mia macchina quando ho iniziato a leggere questo post di blog sui numeri primi. Il codice è in C # e l'algoritmo che ho usato è venuto dalla mia testa sebbene sia probabilmente da qualche parte su Wikipedia. ;) Ad ogni modo, può recuperare i primi 150000 numeri primi in circa 300 ms. Ho scoperto che la somma dei n primi numeri dispari è uguale a n ^ 2. Ancora una volta, c'è probabilmente una prova di ciò da qualche parte su Wikipedia. Quindi, sapendo questo, posso scrivere un algoritmo che non dovrà mai calcolare una radice quadrata, ma devo calcolare in modo incrementale per trovare i numeri primi. Quindi se vuoi l'ennesimo numero primo, questo algo dovrà trovare prima i numeri primi (N-1)! Quindi eccolo. Buon divertimento!
//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
if (count == 0)
return 0;
if (count == 1)
{
if (listPrimes != null)
{
if (!getLast || (count == 1))
listPrimes.Add(2);
}
return count;
}
ulong currentSquare = 1;
ulong nextSquare = 9;
ulong nextSquareIndex = 3;
ulong primesCount = 1;
List dividers = new List();
//Only check for odd numbers starting with 3.
for (ulong curNumber = 3; (curNumber (nextSquareIndex % div) == 0) == false)
dividers.Add(nextSquareIndex);
//Move to next square number
currentSquare = nextSquare;
//Skip the even dividers so take the next odd square number.
nextSquare += (4 * (nextSquareIndex + 1));
nextSquareIndex += 2;
//We may continue as a square number is never a prime number for obvious reasons :).
continue;
}
//Check if there is at least one divider for the current number.
//If so, this is not a prime number.
if (dividers.Exists(div => (curNumber % div) == 0) == false)
{
if (listPrimes != null)
{
//Unless we requested only the last prime, add it to the list of found prime numbers.
if (!getLast || (primesCount + 1 == count))
listPrimes.Add(curNumber);
}
primesCount++;
}
}
return primesCount;
}
Ecco il mio contributo:
Macchina: Quad-Core i7 a 2,4 GHz con 8 GB di RAM a 1600 MHz
Compilatore: clang++ main.cpp -O3
Benchmark:
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100
Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000
Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000
Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000
Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000
Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000
Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000
Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000
Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000
Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$
Fonte:
#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free
using namespace std;
int main(int argc, const char * argv[]) {
if(argc == 1) {
cout << "Please enter a number." << "\n";
return 1;
}
long n = atol(argv[1]);
long i;
long j;
long k;
long c;
long sr;
bool * a = (bool*)malloc((size_t)n * sizeof(bool));
for(i = 2; i < n; i++) {
a[i] = true;
}
clock_t t = clock();
sr = sqrt(n);
for(i = 2; i <= sr; i++) {
if(a[i]) {
for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
a[j] = false;
}
}
}
t = clock() - t;
c = 0;
for(i = 2; i < n; i++) {
if(a[i]) {
//cout << i << " ";
c++;
}
}
cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";
free(a);
return 0;
}
Questo utilizza l'approccio Sieve of Erastothenes, l'ho ottimizzato il più possibile con le mie conoscenze. Miglioramenti benvenuti.
