Code le plus efficace pour les 10 000 premiers nombres premiers ?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je veux imprimer les 10 000 premiers nombres premiers.Quelqu'un peut-il me donner le code le plus efficace pour cela ?Précisions :
- Peu importe si votre code est inefficace pour n >10 000.
- La taille du code n'a pas d'importance.
- Vous ne pouvez pas simplement coder en dur les valeurs de quelque manière que ce soit.
La solution
Le tamis d'Atkin est probablement ce que vous recherchez, sa durée d'exécution limite supérieure est O (N/log log N).
Si vous exécutez uniquement les nombres 1 de plus et 1 de moins que les multiples de 6, cela pourrait être encore plus rapide, car tous les nombres premiers au-dessus de 3 sont à 1 d'un multiple de six.Ressource pour ma déclaration
Autres conseils
Je recommande un tamis, soit le Tamis d'Ératosthène ou la Tamis d'Atkin.
Le tamis ou Eratosthène est probablement la méthode la plus intuitive pour trouver une liste de nombres premiers.En gros vous :
- Écrivez une liste de nombres de 2 à la limite souhaitée, disons 1000.
- Prenez le premier nombre qui n'est pas barré (pour la première itération, c'est 2) et rayez tous les multiples de ce nombre de la liste.
- Répétez l'étape 2 jusqu'à ce que vous atteigniez la fin de la liste.Tous les nombres qui ne sont pas barrés sont premiers.
Évidemment, de nombreuses optimisations peuvent être effectuées pour rendre cet algorithme plus rapide, mais c'est l'idée de base.
Le tamis d'Atkin utilise une approche similaire, mais malheureusement je n'en connais pas assez pour vous l'expliquer.Mais je sais que l'algorithme que j'ai lié prend 8 secondes pour déterminer tous les nombres premiers jusqu'à 1 000 000 000 sur un ancien Pentium II-350.
Tamis d'Eratosthène Code source : http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Tamis du code source d'Atkin : http://cr.yp.to/primegen.html
Ce n'est pas strictement contraire à la restriction de codage en dur, mais s'en rapproche terriblement.Pourquoi ne pas télécharger cette liste par programme et l'imprimer à la place ?
Tueur de portes, que diriez-vous d'ajouter un break pour que if dans le foreach boucle?Cela accélérerait les choses beaucoup parce que si 6 est divisible par 2, vous n'avez pas besoin de vérifier avec 3 et 5.(Je voterais de toute façon pour votre solution si j'avais assez de réputation :-) ...)
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 + " ");
}
}
Chez Haskell, on peut écrire presque mot pour mot la définition mathématique du tamis d'Ératosthène, "les nombres premiers sont des nombres naturels supérieurs à 1 sans nombres composés, où les composés sont trouvés par énumération des multiples de chaque nombre premier":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 est quasi-instantané.
Les références:
Le code ci-dessus est facilement adapté pour fonctionner uniquement sur les cotes, primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)).La complexité temporelle est bien améliorée (à peu près un enregistrer facteur supérieur à l'optimal) en se pliant dans une structure arborescente, et la complexité de l'espace est considérablement amélioré par production d'amorces en plusieurs étapes, dans
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..]
(Dans Haskell, les parenthèses sont utilisées pour le regroupement, un appel de fonction est signifié simplement par juxtaposition, (:) est un les inconvénients opérateur pour les listes, et (.) est un opérateur de composition fonctionnelle : (f . g) x = (\y -> f (g y)) x = f (g x)).
@Mat:log(log(10000)) vaut ~2
Extrait de l'article Wikipédia (que vous avez cité) Tamis d'Atkin:
Ce tamis calcule des nombres premiers à N en utilisant
O(N/log log N)opérations avec seulement n1/2+o(1) des morceaux de mémoire.C'est un peu mieux que le tamis des eratosthènes qui utiliseO(N)opérations et O(N1/2(Journal Journal n) / log n) Bits de mémoire (A.O.L.Atkin, D.J.Bernstein, 2004).Ces complexités de calcul asymptotiques comprennent des optimisations simples, telles que la factorisation des roues et la division du calcul en blocs plus petits.
Compte tenu des complexités informatiques asymptotiques le long O(N) (pour Eratosthène) et O(N/log(log(N))) (pour Atkin) nous ne pouvons pas dire (pour les petits N=10_000) quel algorithme s'il est mis en œuvre sera plus rapide.
Achim Flammenkamp a écrit dans Le tamis d'Ératosthène:
cité par:
@num1
Pour des intervalles plus grands environ 10 ^ 9, sûrement pour ceux> 10 ^ 10, le tamis des eratosthènes est surperformé par le tamis d'Atkins et de Bernstein qui utilise des formes quadratiques binaires irréductibles.Voir leur article pour les informations de base ainsi que le paragraphe 5 de W.Le doctorat de Galway.thèse.
Donc pour 10_000 Le tamis d'Eratosthène peut être plus rapide que le tamis d'Atkin.
Pour répondre à OP, le code est prime_sieve.c (cité par num1)
En utilisant GMP, on pourrait écrire ce qui suit :
#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));
}
}
Sur mon Macbook Pro 2,33 GHz, il s'exécute comme suit :
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
Calcul de 1 000 000 nombres premiers sur le même ordinateur portable :
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP est hautement optimisé pour ce genre de choses.À moins que vous souhaitiez vraiment comprendre les algorithmes en écrivant les vôtres, il vous serait conseillé d'utiliser libGMP sous C.
Pas efficace du tout, mais vous pouvez utiliser une expression régulière pour tester les nombres premiers.
/^1?$|^(11+?)\1+$/
Ceci teste si, pour une chaîne composée de k “1"s, k est pas premier (c'est à dire.si la chaîne est constituée d'un "1" ou n'importe quel nombre de "1» qui peut être exprimé comme un n-produit aire).
J'ai adapté le code trouvé sur le CodeProjet pour créer ce qui suit :
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 + " ");
}
}
Le test sur mon serveur ASP.NET a pris environ 1 minute pour s'exécuter.
Voici un tamis d'Eratosthène que j'ai écrit en PowerShell il y a quelques jours.Il possède un paramètre permettant d'identifier le nombre de nombres premiers qui doivent être renvoyés.
#
# 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
}
Tamis d'Ératosthène est la voie à suivre, en raison de sa simplicité et de sa rapidité.Mon implémentation en 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;
}
Temps CPU pour trouver les nombres premiers (sur Pentium Dual Core E2140 1,6 GHz, utilisant un seul cœur)
~ 4s pour lim = 100 000 000
Adaptation et continuité de Tueur de portes, voici la version finale que j'ai utilisée.
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;
}
C'est fondamentalement la même chose, mais j'ai ajouté la suggestion "pause sur Sqrt" et modifié certaines variables pour qu'elles me conviennent mieux.(Je travaillais sur Euler et j'avais besoin du 10001ème nombre premier)
Le tamis semble être la mauvaise réponse.Le tamis vous donne les nombres premiers jusqu'à un numéro N, pas le n premier prime.Exécutez @Imran ou @Andrew Szeto et vous obtenez les nombres premiers jusqu'à N.
Le tamis peut toujours être utilisable si vous continuez à essayer des tamis pour des nombres de plus en plus grands jusqu'à ce que vous atteigniez une certaine taille de votre ensemble de résultats et que vous utilisiez une mise en cache des nombres déjà obtenus, mais je pense que ce ne serait toujours pas plus rapide qu'une solution comme celle de @Pat. .
En Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
Le algorithme deque tamis mentionné par BenGoldberg mérite d’être examiné de plus près, non seulement parce qu’il est très élégant mais aussi parce qu’il peut parfois être utile en pratique (contrairement au Sieve d’Atkin qui est un exercice purement académique).
L'idée de base derrière l'algorithme du tamis deque est d'utiliser un petit tamis coulissant qui est juste assez grand pour contenir au moins un multiple distinct pour chacun des facteurs premiers actuellement « actifs » - c'est-à-direles nombres premiers dont le carré ne dépasse pas le nombre le plus bas actuellement représenté par le tamis mobile.Une autre différence par rapport au SoE est que le tamis deque stocke les facteurs réels dans les emplacements des composites, et non dans les booléens.
L'algorithme étend la taille de la fenêtre du tamis selon les besoins, ce qui entraîne des performances assez uniformes sur une large plage jusqu'à ce que le tamis commence à dépasser sensiblement la capacité du cache L1 du processeur.Le dernier nombre premier qui correspond parfaitement est 25 237 523 (le 1 579 791ème nombre premier), ce qui donne une estimation approximative de la plage de fonctionnement raisonnable de l’algorithme.
L'algorithme est assez simple et robuste, et il a même des performances sur une plage beaucoup plus large qu'un tamis non segmenté d'Eratosthène.Ce dernier est beaucoup plus rapide tant que son tamis rentre entièrement dans le cache, c'est-à-direjusqu'à 2 ^ 16 pour un tamis à cotes uniquement avec des booléens de la taille d'un octet.Puis ses performances chutent de plus en plus, même s'il reste toujours nettement plus rapide que le deque malgré le handicap (du moins dans les langages compilés comme C/C++, Pascal ou Java/C#).
Voici un rendu de l'algorithme deque sieve en C#, car je trouve ce langage - malgré ses nombreux défauts - beaucoup plus pratique pour le prototypage d'algorithmes et l'expérimentation que le C++ suprêmement lourd et pédant. (Note latérale :J'utilise le gratuit LINQPad ce qui permet de plonger directement, sans tout le désordre lié à la configuration de projets, de makefiles, de répertoires ou autres, et cela me donne le même degré d'interactivité qu'une invite python).
C# n'a pas de type deque explicite mais le simple List<int> fonctionne assez bien pour démontrer l’algorithme.
Note:cette version n'utilise pas de deque pour les nombres premiers, car cela n'a tout simplement pas de sens de retirer sqrt(n) de n nombres premiers.À quoi servirait-il de supprimer 100 nombres premiers et d’en laisser 9900 ?Au moins de cette façon, tous les nombres premiers sont collectés dans un vecteur soigné, prêt pour un traitement ultérieur.
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;
}
}
Voici les deux fonctions d'assistance :
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;
}
La manière la plus simple de comprendre l'algorithme est probablement de l'imaginer comme un tamis segmenté spécial d'Ératosthène avec une taille de segment de 1, accompagné d'une zone de débordement où les nombres premiers s'arrêtent lorsqu'ils dépassent l'extrémité du segment.Sauf que la cellule unique du segment (a.k.a. sieve[0]) a déjà été tamisé lorsque nous y arrivons, car il a été renversé alors qu'il faisait partie de la zone de débordement.
Le nombre représenté par sieve[0] est détenu dans sieve_base, bien que sieve_front ou window_base seraient également de bons noms qui permettent de faire des parallèles avec le code de Ben ou les implémentations de tamis segmentés/fenêtrés.
Si sieve[0] contient une valeur non nulle alors cette valeur est un facteur de sieve_base, qui peut donc être reconnu comme composite.Puisque la cellule 0 est un multiple de ce facteur, il est facile de calculer son prochain saut, qui est simplement 0 plus ce facteur.Si cette cellule est déjà occupée par un autre facteur, nous ajoutons simplement à nouveau le facteur, et ainsi de suite jusqu'à ce que nous trouvions un multiple du facteur là où aucun autre facteur n'est actuellement garé (en étendant le tamis si nécessaire).Cela signifie également qu'il n'est pas nécessaire de stocker les décalages de travail actuels des différents nombres premiers d'un segment au suivant, comme dans un tamis segmenté normal.Chaque fois que nous trouvons un facteur dans sieve[0], son décalage de travail actuel est 0.
Le nombre premier actuel entre en jeu de la manière suivante.Un nombre premier ne peut devenir courant qu'après sa propre apparition dans le flux (c'est-à-direlorsqu'il aura été détecté comme premier, car non marqué d'un facteur), et il restera actuel jusqu'au moment précis où il sieve[0] atteint sa place.Tous les multiples inférieurs de ce nombre premier doivent avoir été radiés en raison des activités de petits nombres premiers, tout comme dans un SoE normal.Mais aucun des nombres premiers les plus petits ne peut rayer le carré, puisque le seul facteur du carré est le nombre premier lui-même et qu'il n'est pas encore en circulation à ce stade.Cela explique les actions entreprises par l'algorithme dans le cas sieve_base == current_prime_squared (ce qui implique sieve[0] == 0, d'ailleurs).
Maintenant le cas sieve[0] == 0 && sieve_base < current_prime_squared s'explique facilement :cela signifie que sieve_base ne peut pas être un multiple d'un des nombres premiers inférieur au nombre premier actuel, sinon il aurait été marqué comme composite.Je ne peux pas non plus être un multiple supérieur du nombre premier actuel, puisque sa valeur est inférieure au carré du nombre premier actuel.Il doit donc s'agir d'un nouveau premier.
L’algorithme s’inspire évidemment du Tamis d’Ératosthène, mais il est tout aussi évidemment très différent.Le Tamis d'Ératosthène tire sa vitesse supérieure de la simplicité de ses opérations élémentaires :un seul ajout d'index et un stockage pour chaque étape de l'opération, c'est tout ce qu'il fait pendant de longues périodes.
Voici un tamis simple et non segmenté d'Eratosthène que j'utilise normalement pour tamiser les facteurs premiers dans la plage ucourte, c'est-à-direjusqu'à 2 ^ 16.Pour cet article, je l'ai modifié pour qu'il fonctionne au-delà de 2 ^ 16 en le remplaçant int pour 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;
}
Lors du tamisage des 10 000 premiers nombres premiers, un cache L1 typique de 32 KiByte sera dépassé mais la fonction est toujours très rapide (fraction de milliseconde même en C#).
Si vous comparez ce code au tamis deque, il est facile de voir que les opérations du tamis deque sont beaucoup plus compliquées et qu'il ne peut pas amortir efficacement ses frais généraux car il effectue toujours la séquence de croisements la plus courte possible d'affilée. (exactement une seule croix, après avoir sauté tous les multiples déjà barrés).
Note:le code C# utilise int au lieu de uint car les compilateurs les plus récents ont l'habitude de générer du code de qualité inférieure pour uint, probablement pour pousser les gens vers les entiers signés...Dans la version C++ du code ci-dessus, j'ai utilisé unsigned partout, naturellement ;le benchmark devait être en C++ car je voulais qu'il soit basé sur un type deque supposément adéquat (std::deque<unsigned>;il n'y a eu aucun gain de performances grâce à l'utilisation unsigned short).Voici les numéros de mon ordinateur portable Haswell (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
Note:les temps C# sont à peu près exactement le double des timings C++, ce qui est plutôt bon pour C# et cela montre que List<int> n'est pas en reste même s'il est abusé comme un deque.
Le simple code du tamis fait toujours exploser le deque hors de l'eau, même s'il fonctionne déjà au-delà de sa plage de fonctionnement normale (taille du cache L1 dépassée de 50 %, avec écrasement du cache qui l'accompagne).La partie dominante ici est la lecture des nombres premiers tamisés, et cela n'est pas beaucoup affecté par le problème de cache.Dans tous les cas, la fonction a été conçue pour filtrer les facteurs de facteurs, c'est-à-direniveau 0 dans une hiérarchie de tamis à 3 niveaux, et il ne doit généralement renvoyer que quelques centaines de facteurs ou un faible nombre de milliers.D'où sa simplicité.
Les performances pourraient être améliorées de plus d'un ordre de grandeur en utilisant un tamis segmenté et en optimisant le code pour extraire les nombres premiers tamisés (mod 3 échelonné et déroulé deux fois, ou mod 15 et déroulé une fois), et encore plus de performances pourraient être extraites de le code en utilisant une molette mod 16 ou mod 30 avec tous les accompagnements (c.-à-d.déroulement complet pour tous les résidus).Quelque chose comme ça est expliqué dans ma réponse à Trouver un nombre premier en position première sur Code Review, où un problème similaire a été discuté.Mais il est difficile de voir l’intérêt d’améliorer les temps inférieurs à la milliseconde pour une tâche ponctuelle…
Pour mettre les choses un peu en perspective, voici les timings C++ pour filtrer jusqu'à 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
En revanche, un tamis segmenté en C# avec quelques cloches et sifflets fait le même travail en 95 ms (aucun timing C++ disponible, puisque je fais des défis de code uniquement en C# pour le moment).
Les choses peuvent paraître résolument différentes dans un langage interprété comme Python, où chaque opération a un coût élevé et où la surcharge de l'interpréteur éclipse toutes les différences dues aux prévisions et aux prévisions.branches mal prédites ou opérations de sous-cycle (changement, ajout) vs.opérations multicycles (multiplication, et peut-être même division).Cela ne manquera pas d'éroder l'avantage de simplicité du tamis d'Ératosthène, ce qui pourrait rendre la solution deque un peu plus attrayante.
En outre, bon nombre des timings rapportés par d'autres répondants sur ce sujet sont probablement dominés par temps de sortie.C'est une guerre complètement différente, où mon arme principale est une classe simple comme celle-ci :
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;
}
}
}
Cela prend moins de 1 ms pour écrire 10 000 nombres (triés).Il s'agit d'une classe statique car elle est destinée à l'inclusion textuelle dans les soumissions de défis de codage, avec un minimum de complications et aucune surcharge.
En général, j'ai trouvé que c'était beaucoup plus rapide si un travail ciblé est effectué sur des lots entiers, c'est-à-dire tamiser une certaine plage, puis extraire tous les nombres premiers dans un vecteur/tableau, puis éliminer l'ensemble du tableau, puis tamiser la plage suivante et ainsi de suite, au lieu de tout mélanger.Le fait d'avoir des fonctions distinctes axées sur des tâches spécifiques facilite également la combinaison, permet la réutilisation et facilite le développement/les tests.
Voici mon code VB 2008, qui trouve tous les nombres premiers <10 000 000 en 1 min 27 secondes sur mon ordinateur portable de travail.Il ignore les nombres pairs et recherche uniquement les nombres premiers < le carré du numéro de test.Il est uniquement conçu pour trouver des nombres premiers de 0 à une valeur sentinelle.
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
Le code Mathcad suivant a calculé le premier million de nombres premiers en moins de 3 minutes.
Gardez à l’esprit que cela utiliserait des doubles à virgule flottante pour tous les nombres et que cela serait essentiellement interprété.J'espère que la syntaxe est claire.
Voici une solution C++, utilisant une forme de 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;
}
Notez que cette version du Sieve peut calculer les nombres premiers indéfiniment.
A noter également, la STL deque prend O(1) il est temps d'effectuer push_back, pop_front, et accès aléatoire via abonnement.
Le resize l'opération prend O(n) le temps, où n est le nombre d'éléments ajoutés.En raison de la façon dont nous utilisons cette fonction, nous pouvons considérer qu'il s'agit d'une petite constante.
Le corps du while boucle dans my_insert est exécuté O(log log n) fois, où n est égal à la variable maybe_prime.Cela est dû au fait que l’expression conditionnelle du while sera évalué à vrai une fois pour chaque facteur premier de maybe_prime.Voir "Fonction diviseur" sur Wikipédia.
Multiplier par le nombre de fois my_insert est appelé, montre que cela devrait prendre O(n log log n) il est temps de lister n primes...ce qui est, sans surprise, la complexité temporelle que le tamis d'Ératosthène est censé avoir.
Cependant, même si ce code est efficace, ce n'est pas le le plus efficace...Je suggère fortement d'utiliser une bibliothèque spécialisée pour la génération de nombres premiers, telle que tamis d'amorçage.Toute solution vraiment efficace et bien optimisée nécessitera plus de code que quiconque ne voudrait saisir dans Stackoverflow.
En utilisant le tamis d'Eratosthène, le calcul est bien plus rapide que l'algorithme des nombres premiers « à l'échelle connue ».
En utilisant le pseudocode de son wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), je peux avoir la solution en 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) prend 2 s et 330 ms.
NOTE:La valeur peut varier en fonction des spécifications matérielles.
Je passe du temps à écrire un programme calculant de nombreux nombres premiers et c'est le code que j'utilise pour calculer un fichier texte contenant les 1 000 000 000 premiers nombres premiers.C'est en allemand, mais ce qui est intéressant c'est la méthode calcPrimes().Les nombres premiers sont stockés dans un tableau appelé Primzahlen.Je recommande un processeur 64 bits car les calculs se font avec des entiers 64 bits.
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);
}
}
}
J'ai écrit ceci en utilisant Python, car je viens de commencer à l'apprendre, et cela fonctionne parfaitement.Le 10 000ème nombre premier généré par ce code comme celui mentionné dans http://primes.utm.edu/lists/small/10000.txt.Pour vérifier si n est premier ou non, divise n par les chiffres de 2 à sqrt(n).Si l'un des nombres de cette plage divise parfaitement n alors ce n'est pas premier.
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))
Je travaille sur la recherche de nombres premiers depuis environ un an.Voici ce que j'ai trouvé le plus rapide :
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 secondes pour arriver à 2147483629 à partir de 2 heures.
Voici mon code qui trouve les 10 000 premiers nombres premiers en 0,049655 sec sur mon ordinateur portable, 1 000 000 premiers nombres premiers en moins de 6 secondes et 2 000 000 premiers en 15 secondes
Une petite explication.Cette méthode utilise 2 techniques pour trouver un nombre premier
- tout d'abord, tout nombre non premier est un composé de multiples de nombres premiers, donc ce code teste en divisant le nombre de test par des nombres premiers plus petits au lieu de n'importe quel nombre, cela diminue le calcul d'au moins 10 fois pour un nombre à 4 chiffres et encore plus pour un plus grand nombre
- deuxièmement, en plus de diviser par nombre premier, il divise uniquement par des nombres premiers qui sont plus petits ou égaux à la racine du nombre testé, réduisant encore considérablement les calculs, cela fonctionne car tout nombre supérieur à la racine du nombre aura un nombre homologue qui doit être inférieur à la racine du nombre, mais comme nous avons déjà testé tous les nombres inférieurs à la racine, nous n'avons donc pas besoin de nous soucier d'un nombre supérieur à la racine du nombre testé.
Exemple de sortie pour les 10 000 premiers nombres premiers
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
Voici le code en C, entrez 1 puis 10 000 pour imprimer les 10 000 premiers nombres premiers.
Modifier:J'ai oublié que cela contient une bibliothèque mathématique, si vous êtes sous Windows ou Visual Studio, cela devrait aller, mais sous Linux, vous devez compiler le code en utilisant l'argument -lm ou le code risque de ne pas fonctionner.
Exemple:gcc -Wall -o "%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);
}
Voici le code que j'ai fait :
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;
}
Utilisation de la méthode Array.prototype.find() en 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
Je peux vous donner quelques conseils, il faut les mettre en œuvre.
- Pour chaque nombre, obtenez la moitié de ce nombre.Par exemple.pour vérifier 21, obtenez uniquement le reste en le divisant par la plage 2-10.
- S'il s'agit d'un nombre impair, divisez uniquement par un nombre impair, et vice versa.Par exemple pour 21, divisez par 3, 5, 7, 9 seulement.
Méthode la plus efficace que j’ai utilisée jusqu’à présent.
Puisque vous ne voulez que les 10000 premiers nombres premiers, plutôt que le codage de l'algorithme complexe, je suggérerai ce qui suit
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;
}
maintenant, l'appel est prioritaire car vous en avez besoin
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
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();
}
}
}
