Calcul du nombre premier amusant
https://stackoverflow.com/questions/288200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Nous nous amusons un peu ici au travail. Tout a commencé avec l’un des gars qui a installé un Hackintosh et nous nous demandions si c’était plus rapide qu’une Windows Box avec (presque) les mêmes spécifications que nous avons. Nous avons donc décidé d'écrire un petit test pour cela. Juste une simple calculatrice de nombres premiers. Il est écrit en Java et indique le temps nécessaire pour calculer les n premiers nombres premiers.
Version optimisée ci-dessous - prend maintenant environ 6.6 secondes
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);
}
}
Nous avons à peu près perdu l'intrigue de l'ensemble du problème Hackintosh vs PC et nous nous amusons simplement à l'optimiser. La première tentative sans optimisation (le code ci-dessus en a deux) a duré environ 52,6 minutes pour trouver les 150000 premiers nombres premiers. Cette optimisation tourne autour de 47,2 minutes.
Si vous voulez essayer vos résultats et les publier, collez-les.
Les spécifications du PC sur lequel je travaille sont le Pentium D 2,8 GHz, 2 Go de RAM et Ubuntu 8.04.
La meilleure optimisation jusqu'à présent est la racine carrée du courant, mentionnée pour la première fois par Jason Z.
La solution
Eh bien, je vois quelques optimisations rapides qui peuvent être effectuées. D'abord, vous n'êtes pas obligé d'essayer chaque numéro jusqu'à la moitié du nombre actuel.
Au lieu de cela, vous n'avez qu'à essayer jusqu'à la racine carrée du numéro actuel.
Et l'autre optimisation était ce que BP a dit avec une torsion: Au lieu de
int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
current++;
else
current += 2;
utiliser
int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;
Cela devrait accélérer beaucoup les choses.
Modifier:
Plus d'optimisation offerte par Joe Pineda:
Supprimez la variable & "Top &";
int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;
Si cette optimisation augmente effectivement, la vitesse passe à java.
Le calcul de la racine carrée prend beaucoup de temps par rapport à la multiplication de deux nombres. Cependant, puisque nous déplaçons la multiplication dans la boucle for, cela se fait à chaque boucle. Cela pourrait donc ralentir les choses en fonction de la rapidité de l'algorithme de racine carrée en Java.
Autres conseils
C’est un peu pire que mon tamis sur un 8 Mhz 8088 en turbo pascal en 1986 ou à peu près. Mais c’était après optimisations:)
Puisque vous les recherchez par ordre croissant, vous pouvez conserver une liste des nombres premiers que vous avez déjà trouvés et ne vérifier que la divisibilité par rapport à eux, car tous les nombres non premiers peuvent être réduits à une liste de nombres premiers inférieurs. les facteurs. Si vous combinez cela avec le conseil précédent, qui consiste à ne pas rechercher les facteurs sur la racine carrée du nombre actuel, vous obtiendrez une implémentation extrêmement efficace.
Voici une solution simple et rapide:
- Recherche de nombres premiers inférieurs à 100 000; 9592 ont été trouvés en 5 ms
- Recherche de nombres premiers inférieurs à 1000000; 78498 ont été trouvés en 20 ms
- Recherche de nombres premiers inférieurs à 10000000; 664579 ont été trouvés en 143 ms
- Recherche de nombres premiers inférieurs à 100000000; 5761455 ont été trouvés en 2024 m
-
Recherche de nombres premiers inférieurs à 1000000000; 50847534 ont été trouvés dans 23839 m
//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(); }
Il nous faut moins d’une seconde (2,4 GHz) pour générer les 150000 premiers nombres premiers en Python en utilisant 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]))
Exemple:
$ 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]
En 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;
}
}
Sortie:
Temps total pris: 2,087 secondes
Gardant à l'esprit qu'il existe de meilleurs moyens de rechercher des nombres premiers ...
Je pense que vous pouvez prendre cette boucle:
for (int i = 2; i < top; i++)
et faites en sorte que votre variable de compteur i passe de 3 et tente uniquement de faire le mod sur les nombres impairs, car tous les nombres premiers autres que 2 ne sont jamais divisibles par un nombre pair.
Est-ce que la re-déclaration de la variable prime
while (count < topPrime) {
boolean prime = true;
dans la boucle le rendre inefficace? (Je suppose que cela n'a pas d'importance, car j'estime que Java optimiserait cela)
boolean prime;
while (count < topPrime) {
prime = true;
C #
Amélioration du code d'Aistina :
Cela tient compte du fait que tous les nombres premiers supérieurs à 3 ont la forme 6n + 1 ou 6n - 1.
Il s’agit d’une augmentation de la vitesse de 4 à 5% par incrément de 1 à chaque passage dans la boucle.
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;
}
}
Mon point de vue de l'optimisation, en évitant les astuces trop cryptiques. J'utilise le truc donné par I-GIVE-TERRIBLE-ADVICE, que je connaissais et que j'avais oublié ...: -)
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();
}
}
Oui, j'ai utilisé la mention Continuer, la première fois que je les ai essayés en Java ...
Je sais que je saute le calcul des premiers nombres premiers, mais ils sont bien connus, inutile de les recalculer. :-) Je peux coder en dur leur sortie si nécessaire! En plus, cela ne donne pas un avantage décisif de toute façon.
Résultats:
- Premier
Dernier prime = 2015201
Temps total = 4.281
- Deuxième
Dernier prime = 2015201
Temps total = 0,953
Pas mal. Je suppose qu’il pourrait être amélioré, mais trop d’optimisation peut tuer un bon code.
Vous devriez pouvoir réaliser la boucle interne deux fois plus vite en évaluant uniquement les nombres impairs. Pas sûr que ce soit valide en Java, je suis habitué au C ++, mais je suis sûr que cela peut être adapté.
if (current != 2 && current % 2 == 0)
prime = false;
else {
for (int i = 3; i < top; i+=2) {
if (current % i == 0) {
prime = false;
break;
}
}
}
J'ai décidé d'essayer cela en fa #, ma première tentative décente. À l’aide du tamis d’Ératosthène sur mon 2.2Ghz Core 2 Duo, il parcourt une distance de 2,150 000 en environ 200 millisecondes. Chaque fois qu'il appelle lui-même, il supprime les multiples actuels de la liste, ce qui accélère le processus. C’est l’un de mes premiers essais en fa #, donc tout commentaire constructif serait apprécié.
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
Voici ma solution ... c'est assez rapide ... il calcule les nombres premiers entre 1 et 10 000 000 en 3 secondes sur ma machine (Core i7 @ 2.93Ghz) sous Vista64.
Ma solution est en C, mais je ne suis pas un programmeur C professionnel. N'hésitez pas à critiquer l'algorithme et le code lui-même:)
#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;
}
Voici mon point de vue. Le programme est écrit en C et prend 50 millisecondes sur mon ordinateur portable (Core 2 Duo, 1 Go de RAM). Je garde tous les nombres premiers calculés dans un tableau et je n’essaie de divisibilité que jusqu’à sqrt de nombre. Bien sûr, cela ne fonctionne pas lorsque nous avons besoin d’un très grand nombre de nombres premiers (essayé avec 100000000) car le tableau devient trop grand et donne une erreur de segmentation.
/*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 - ne savez pas s'il s'agit de code java
Ils vont se plaindre peut-être mais je souhaitais réécrire en utilisant le paradigme que j’ai appris à faire confiance à Java et ils ont dit de s’amuser, assurez-vous qu’ils comprennent bien que la spécification ne dit rien qui affecte les commandes renvoyé le jeu de résultats, vous devez également convertir les valeurs de points du jeu de résultats () en un type de liste donné mon unique dans le Bloc-notes avant de prendre une petite course
=============== commencer le code non testé ===============
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 ....
}
=============== Fin du code non testé ================
L'utilisation de jeux de hachages permet de rechercher les résultats sous forme d'arborescence B-Arbre. Ainsi, les résultats peuvent être empilés jusqu'à ce que la machine commence à échouer, puis ce point de départ peut être utilisé pour un autre bloc de test == la fin d'une exécution utilisée en tant que valeur du constructeur. pour une autre exécution, persister sur le travail sur disque déjà accompli et permettre des conceptions incrémentielles à feed-forward. Crevé, la logique de la boucle nécessite une analyse.
patch (plus add 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
J'ai trouvé ce code quelque part sur ma machine lorsque j'ai commencé à lire cette entrée de blog concernant les nombres premiers. Le code est en C # et l'algorithme que j'ai utilisé vient de ma tête même s'il est probablement quelque part sur Wikipedia. ;) Quoi qu'il en soit, il peut récupérer les 150000 premiers nombres premiers en environ 300 ms. J'ai découvert que la somme des n premiers nombres impairs est égale à n ^ 2. Encore une fois, il existe probablement une preuve de cela quelque part sur wikipedia. Sachant cela, je peux écrire un algorithme qui ne devra jamais calculer une racine carrée, mais de manière incrémentielle pour trouver les nombres premiers. Donc si vous voulez le Nième nombre premier, cet algo devra trouver les nombres premiers précédents (N-1) avant! Tiens voilà. Profitez!
//
// 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;
}
Voici ma contribution:
Ordinateur: Quad-Core i7 à 2,4 GHz avec 8 Go de RAM à 1600 MHz
Compilateur: clang++ main.cpp -O3
Points de repère:
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$
Source:
#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;
}
Ceci utilise l’approche Sieve of Erastothenes, je l’optimise autant que je peux avec mes connaissances. Les améliorations sont les bienvenues.
