Le code le plus efficace pour les premiers 10000 nombres premiers?
je veux imprimer les premiers 10000 nombres premiers. Est-ce que quelqu'un peut me donner le code le plus efficace pour ça? Précisions:
- peu importe si votre code est inefficace pour n >10000.
- La taille du code n'a pas d'importance.
- vous ne pouvez pas simplement code dur les valeurs de n'importe quelle manière.
27 réponses
le tamis D'Atkin est probablement ce que vous cherchez, sa limite supérieure de temps de fonctionnement est O(N/log n).
si vous exécutez seulement les nombres 1 de plus et 1 de moins que les multiples de 6, il pourrait être encore plus rapide, comme tous les nombres premiers au-dessus de 3 sont 1 loin d'un certain multiple de six. Ressource pour ma déclaration
je recommande un tamis, soit le tamis D'Eratosthène ou le tamis D'Atkin.
le tamis ou Eratosthène est probablement la méthode la plus intuitive pour trouver une liste de nombres premiers. Fondamentalement vous:
- Écrivez une liste de nombres de 2 à quelque limite que vous voulez, disons 1000.
- prendre le premier numéro 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'à la fin de la liste. Tous les nombres qui ne sont pas rayés sont premiers.
évidemment, il y a pas mal d'optimisations qui peuvent être faites pour rendre cet algorithme plus rapide, mais c'est l'idée de base.
Le crible d'Atkin utilise une approche similaire, mais malheureusement, je ne connais pas assez pour l'expliquer pour vous. Mais je sais que l'algorithme j'ai relié prend 8 secondes pour comprendre tous les nombres premiers jusqu'à 1000000000 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 D'Atkin code Source: http://cr.yp.to/primegen.html
ce n'est pas strictement contre la restriction du codage, mais est terriblement proche. Pourquoi ne pas télécharger cette liste et l'imprimer à la place?
GateKiller , Que diriez-vous d'ajouter un break à ce if dans la boucle foreach ? Cela accélérerait les choses beaucoup parce que si comme 6 est divisible par 2 vous n'avez pas besoin de vérifier avec 3 et 5. (Je voterais votre solution de toute façon 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 + " ");
}
}
dans Haskell, nous pouvons écrire presque mot pour mot la définition mathématique du tamis de Eratosthènes, " les nombres premiers sont des nombres naturels au-dessus de 1 sans aucun nombre composite, où les composites sont trouvés par l'énumération des multiples de chaque prime ":
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 est presque instantané.
, les Références:
le code ci-dessus est facilement modifié dans le travail sur les cotes seulement, 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é du temps est considérablement améliorée (à peu près un log facteur au-dessus optimal) en se pliant dans une structure arborescente, et l'espace la complexité est drastically improved par production de primes à 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 groupement, un appel de fonction est signifié juste par juxtaposition, (:) est un cons opérateur de listes, et (.) est un opérateur de composition fonctionnelle: (f . g) x = (\y -> f (g y)) x = f (g x) ).
@Matt: log (log (10000)) est ~2
D'après l'article de wikipedia (que vous avez cité) tamis D'Atkin :
ce tamis calcule des nombres premiers jusqu'À N utilisation des opérations
O(N/log log N)avec seulement N 1/2+o (1) bits de mémoire. C'est un peu mieux que le tamis de Eratosthènes qui utilisentO(N)opérations et O (N 1/2 (log n) / log N) bits of memory (A. O. L. Atkin, D. J. Bernstein, 2004) . Ces asymptotiques calcul des complexités inclure des optimisations simples, comme la roue la factorisation et la calcul de blocs plus petits.
étant donné les complexités computationnelles asymptotiques le long de O(N) (pour les Eratosthènes) et O(N/log(log(N))) (pour L'Atkin) nous ne pouvons pas dire (pour le petit N=10_000 ) quel algorithme si mis en œuvre sera plus rapide.
Achim Flammenkamp écrit dans le tamis D'Eratosthène :
cité par:
@num1
pour des intervalles plus grands d'environ 10^9, pour ceux qui ont plus de 10^10 ans, le tamis de Eratosthène est surperformé par le Tamis D'Atkins et de Bernstein qui utilise irréductible binaire quadratique forme. Voir leur article pour plus d'information informations ainsi que le paragraphe 5 de Le doctorat de W. Galway thèse.
donc pour 10_000 le tamis D'Eratosthène peut être plus rapide que le tamis D'Atkin.
pour répondre au 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 de 2,33 GHz, il s'exécute comme suit:"
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
calculant 1.000.000 de 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 chose. A moins que vous ne vouliez vraiment comprendre les algorithmes en écrivant les vôtres, il vous serait conseillé d'utiliser libGMP sous C.
j'ai adapté le code trouvé sur le CodeProject 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 + " ");
}
}
Testing this on my ASP.NET le serveur a mis environ 1 minute à tourner.
Pas efficace du tout, mais vous pouvez utiliser une expression régulière pour tester des nombres premiers.
/^1?$|^(11+?)+$/
ce test si, pour une chaîne consistant en k 1 " s, k est pas premier (c'est-à-dire si la chaîne consiste en un 1 "ou un nombre quelconque de" 1 "s qui peuvent être exprimés comme un n - ary produit).
voici un tamis D'Eratosthènes que j'ai écrit dans PowerShell il y a quelques jours. Il a un paramètre pour identifier le nombre de nombres premiers qui doivent être retourné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'Eratosthène est la voie à suivre, en raison de sa simplicité et de sa vitesse. Ma mise en œuvre 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;
}
CPU de Temps pour trouver les nombres premiers (sur les Pentium Dual Core E2140 1.6 GHz, en utilisant un seul core)
~ 4s pour lim = 100 000 000 d'
adaptation et suite de GateKiller , voici la version finale que j'ai utilisé.
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 essentiellement la même chose, mais j'ai ajouté la suggestion" break on Sqrt " et changé certaines des variables autour pour le rendre mieux adapté pour moi. (Je travaillais sur d'Euler et ont besoin de la 10001th premier)
le tamis semble être la mauvaise réponse. Le tamis vous donne les nombres premiers jusqu'à un nombre N , pas les nombres premiers n . Courir @Imran ou @Andrew Szeto, et vous obtenez les primes jusqu'à N.
le tamis pourrait encore ê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 jeu de résultats, et d'utiliser une certaine mise en cache des nombres déjà obtenus, mais je crois il ne serait toujours pas plus rapide qu'une solution comme @Pat.
En Python
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
le algorithme de crible deque mentionné par BenGoldberg mérite un regard plus attentif, non seulement parce qu'il est très élégant, mais aussi parce qu'il peut parfois être utile dans la pratique (contrairement au crible D'Atkin, qui est un exercice purement académique).
l'idée de base derrière l'algorithme de crible deque est d'utiliser un petit Crible coulissant qui est seulement assez grand pour contenir au moins un multiple séparé pour chacun des actuellement "actif" facteurs principaux-c.-à-d. les 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 de la SoE est que le tamis deque stocke les facteurs réels dans les fentes des composites, pas booléens.
l'algorithme étend la taille de la fenêtre du tamis selon les besoins, ce qui permet d'obtenir des performances relativement égales sur une large plage jusqu'à ce que le tamis commence à dépasser de façon appréciable la capacité du cache L1 du CPU. Le dernier, le premier qui fits fully est de 25,237,523 (le 1,579,791 St prime), ce qui donne un chiffre approximatif pour la plage de fonctionnement raisonnable de l'algorithme.
l'algorithme est assez simple et robuste, et il a même la performance sur une gamme beaucoup plus large qu'un tamis non segmenté D'Eratosthènes. Ce dernier est beaucoup plus rapide tant que son tamis s'insère complètement dans le cache, c'est-à-dire jusqu'à 2^16 pour un tamis de cotes avec des bools de taille byte. Puis sa performance baisse de plus en plus, bien qu'il reste toujours significativement plus rapide que la deque malgré le handicap (au moins dans les langages compilés comme C/C++, Pascal ou Java/C#).
voici un rendu de l'algorithme de crible en C#, parce que je trouve que le langage - malgré ses nombreux défauts - est beaucoup plus pratique pour le prototypage des algorithmes et l'expérimentation que le c++extrêmement lourd et pédant. (Sidenote: j'utilise le free LINQPad qui permet de plonger directement dans, sans tout le désordre avec la mise en place de projets, makefiles, répertoires ou autres, et ça 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 sortir sqrt(n) de n nombres premiers. Quel bon serait-il supprimer 100 nombres premiers et de laisser 9900? Au moins de cette façon, tous les nombres premiers sont collectés dans un vecteur propre, 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'aide:
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;
}
probablement la façon la plus facile de comprendre l'algorithme est de l'imaginer comme un tamis segmenté spécial D'Eratosthènes avec un segment de taille de 1, accompagné d'une zone de débordement où les nombres premiers viennent se reposer quand ils tirent au cours de la fin du segment. Sauf que la seule cellule du segment (A. K. A. sieve[0] ) a déjà été tamisé lorsque nous y sommes arrivés, parce qu'il a été écrasé alors qu'il faisait partie de la zone de débordement.
le nombre qui est représenté par sieve[0] est détenu dans sieve_base , bien que sieve_front ou window_base serait également de bons Noms qui permettent de tracer des parallèles avec le code de Ben ou des implémentations de tamis segmentés/fendus.
si sieve[0] contient une valeur non nulle , alors cette valeur est un facteur de sieve_base , qui peut donc être considérée comme composite. Puisque la cellule 0 est un multiple de ce facteur, il est facile de calculer son hop suivant, qui est tout simplement 0 plus ce facteur. Si cette cellule est déjà occupée par un autre facteur, alors nous ajoutons simplement le facteur à nouveau, et ainsi de suite jusqu'à ce que nous trouvions un multiple du facteur où aucun autre facteur n'est actuellement stationné (extension du tamis si nécessaire). Cela signifie également qu'il n'est pas nécessaire pour stocker les offsets de travail courants des différents nombres premiers d'un segment à l'autre, 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 prime actuel entre en jeu de la manière suivante. Un prime ne peut devenir courant qu'après sa propre occurrence dans le flux (c'est-à-dire lorsqu'il a été détecté comme premier, parce qu'il n'est pas marqué d'un facteur), et il restera courant jusqu'au moment exact où sieve[0] atteint sa place. Tous les multiples inférieurs de ce prime doivent avoir été rayés en raison des activités des petits nombres premiers, tout comme dans un SoE normal. Mais aucun des petits nombres premiers ne peut rayer le carré, puisque le seul facteur du carré est le premier lui-même et il n'est pas encore en circulation à ce point. Cela explique les actions prises par l'algorithme dans le cas sieve_base == current_prime_squared (qui implique sieve[0] == 0 , soit dit en passant).
Maintenant le cas sieve[0] == 0 && sieve_base < current_prime_squared s'explique facilement: cela signifie que sieve_base ne peut être un multiple d'aucun des nombres premiers plus petit que le nombre premier actuel, ou bien il aurait été marqué comme composé. Je ne peux pas non plus être un multiple supérieur du premier actuel, puisque sa valeur est inférieure au carré du premier actuel. Il doit donc être un nouveau Premier.
l'algorithme est évidemment inspiré par le tamis D'Eratosthène, mais également de toute évidence il est très différent. Le tamis D'Eratosthène tire son une vitesse supérieure à la simplicité de ses opérations élémentaires: un indice de plus et d'un magasin pour chaque étape de l'opération est tout ce qu'il fait pendant de longues périodes de temps.
voici un tamis simple, non segmenté, d'Eratosthènes que j'utilise normalement pour tamiser des nombres premiers dans la gamme ushort, c'est-à-dire jusqu'à 2^16. Pour ce post, je l'ai modifié pour travailler au-delà de 2^16 en remplaçant int par ushort 1519320920"
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 premiers 10000 nombres premiers, une cache L1 typique de 32 Kibytes sera dépassée, mais la fonction est encore très rapide (fraction d'une milliseconde même en C#).
si vous comparez ce code au tamis deque, alors il est facile de voir que les opérations du tamis deque sont beaucoup plus compliquées, et il ne peut pas amortir efficacement ses frais généraux parce qu'il fait toujours le plus court tronçon possible de croisements-off dans une rangée (exactement un seul croisement-off, après sauter tous les multiples qui ont été rayés déjà).
Note: le code C utilise int au lieu de uint parce que les nouveaux compilateurs ont l'habitude de générer un code inférieur à la norme pour uint , probablement pour pousser les gens vers des entiers signés... Dans la version C++ du code ci-dessus j'ai utilisé unsigned tout au long, naturellement; le benchmark devait être en C++ parce que je voulais qu'il soit basé sur un type deque supposé adéquat ( std::deque<unsigned> ; il n'y a pas eu de gain de rendement en utilisant unsigned short ). Voici les numéros de mon 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 temps C++, ce qui est assez bon pour C# et ìt montre que List<int> n'est pas slouch même si abusé comme une déque.
le simple code de tamis souffle encore le deque hors de l'eau, même s'il fonctionne déjà au-delà de sa portée normale (L1 cache la taille est dépassée de 50%, et le cache est fracassé). La partie dominante ici est la lecture des nombres premiers tamisés, et ceci n'est pas affecté par le problème de cache. Dans tous les cas, la fonction a été conçue pour tamiser les facteurs de facteurs, c'est-à-dire le niveau 0 dans une hiérarchie de tamis à trois niveaux, et en général, elle ne doit retourner que quelques centaines de facteurs ou un petit nombre de milliers. D'où sa simplicité.
La Performancepourrait être améliorée de plus d'un ordre de grandeur par en utilisant un tamis segmenté et en optimisant le code pour extraire les nombres premiers tamisés (pas mod 3 et déroulés deux fois, ou mod 15 et déroulés une fois) , et encore plus de performance pourrait être retirée du code en utilisant une roue mod 16 ou mod 30 avec tous les garnitures (c'est-à-dire entièrement déroulante pour tous les résidus). Quelque chose comme cela est expliqué dans ma réponse à trouver le nombre premier positionné sur la révision du Code, où un problème similaire a été discuté. Mais il est difficile de voir le point d'améliorer les temps de sous-milliseconde pour une tâche unique...
pour mettre les choses un peu en perspective, voici les temps C++ pour tamiser 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
par contraste, un tamis segmenté en C# avec quelques cloches et sifflets fait le même travail en 95 ms (pas de chronométrage C++ disponible, puisque je ne conteste le code qu'en C# en ce moment).
les choses peuvent sembler très différentes dans une interprétation un langage comme Python où chaque opération a un coût élevé et l'interpréteur overhead éclipse toutes les différences dues aux branches prédites ou mal interprétées ou aux opérations de sous-cycle (shift, addition) par rapport aux opérations de multi-cycle (multiplication, et peut-être même division). Cela doit éroder l'avantage de simplicité du tamis D'Eratosthène, et cela pourrait rendre la solution deque un peu plus attrayant.
en outre, un grand nombre des horaires rapportés par d'autres répondants dans ce sujet sont probablement dominé par sortie du temps . C'est une guerre entièrement 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;
}
}
}
qui prend moins de 1 ms pour écrire 10000 numéros (triés). Il s'agit d'une classe statique parce qu'elle est prévue pour l'inclusion textuelle dans les soumissions de contestation de codage, avec un minimum de tracas et zéro frais généraux.
en général, je l'ai trouvé à être beaucoup plus rapide si le travail focalisé est fait sur des lots entiers, c'est-à-dire tamiser une certaine gamme, puis extraire tous les nombres premiers dans un vecteur/réseau, puis éjecter l'ensemble du réseau, puis tamiser la gamme suivante et ainsi de suite, au lieu de tout mélanger. Le fait d'avoir des fonctions distinctes axées sur des tâches précises facilite également le mélange et l'appariement, permet la réutilisation et facilite le développement et les essais.
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 saute des nombres pairs et ne cherche que des nombres premiers qui sont < le sqrt du nombre de test. Il est seulement 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 ce serait en utilisant des doubles à virgule flottante pour tous les nombres et est essentiellement interprété. J'espère que la syntaxe est claire.
Voici une solution C++, en 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 tamis peut calculer des nombres premiers indéfiniment.
a noter Aussi, le TSL deque prend O(1) de temps à effectuer push_back , pop_front , d'accès aléatoire et si subscripting.
l'opération resize prend O(n) temps, où n est le nombre d'éléments ajoutés. En raison de la façon dont nous utilisez cette fonction, nous pouvons le traiter est une petite constante.
le corps de la boucle while dans my_insert est exécuté O(log log n) fois, où n égale la variable maybe_prime . C'est parce que l'expression de condition du while évaluera à vrai une fois pour chaque facteur principal de maybe_prime . Voir " Diviseur de la fonction " sur Wikipédia.
multiplié par le nombre de fois my_insert est appelé, montre qu'il devrait prendre O(n log log n) temps d'énumérer n nombres premiers... ce qui est, sans surprise, la complexité temporelle que le tamis D'Eratosthène est censé avoir.
cependant, alors que ce code est efficace, ce n'est pas le le plus efficace ... Je suggère fortement l'utilisation d'une bibliothèque spécialisée pour la génération des nombres premiers, comme primesieve . Tout vraiment solution efficace, bien optimisé, prendra plus de code que quiconque veut entrer dans Stackoverflow.
à L'aide de tamis D'Eratosthènes, le calcul est beaucoup plus rapide par rapport à l'algorithme des nombres premiers "connus à l'échelle".
en utilisant le pseudocode de son wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), je peux avoir la solution sur 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 2s et 330ms.
NOTE : la valeur peut varier en fonction sur les spécifications du matériel.
je passe un certain temps à écrire un programme calculant beaucoup de nombres premiers et c'est le code que je suis utilisé pour calculer un fichier texte contenant les premiers 1.000.000.000 nombres premiers. C'est en allemand, mais la partie intéressante est la méthode calcPrimes() . Les nombres premiers sont stockés dans un tableau appelé Primzahlen. Je recommande un CPU 64bit parce que les calculs sont avec des entiers 64bit.
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, comme je viens de commencer à l'apprendre, et ça fonctionne parfaitement bien. Le 10 000e premier produit par ce code comme indiqué dans http://primes.utm.edu/lists/small/10000.txt . Pour vérifier si n est Premier ou non, divisez n par les nombres de 2 à sqrt(n) . Si l'un de ces nombres divise parfaitement n alors il 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 find primes depuis environ un an. C'est 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 2147483629 à partir de 2.
Voici mon code qui trouve
les 10.000 premiers nombres premiers en 0.049655 sec sur mon ordinateur portable, les 1.000.000 premiers en moins de 6 secondes et les 2.000.000 premiers en 15 secondes
Une petite explication. Cette méthode utilise 2 techniques pour trouver le nombre premier
- tout d'abord n'importe quel nombre de non-prime est un composé de multiples de nombres premiers ainsi ce test de code en divisant le nombre de test par des nombres premiers plus petits au lieu de n'importe quel nombre, ceci diminue calcul par au moins 10 fois pour un nombre à 4 chiffres et encore plus pour un nombre plus grand
- deuxièmement en plus de diviser par Premier, il divise seulement par nombres premiers qui sont plus petits ou égaux à la racine du nombre testé réduire davantage les calculs beaucoup, cela fonctionne parce que n'importe quel nombre qui est plus grand que la racine du nombre aura un nombre de contrepartie qui doit être plus petit que la racine du nombre mais puisque nous avons testé tous les nombres plus petits que la racine déjà, donc nous n'avons pas besoin de nous embêter avec un nombre plus grand que la racine du nombre testé.
sortie de L'échantillon pour les premiers 10 000 nombres premiers
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
voici le code en langage C,
Entrer 1 et 10.000 pour imprimer le 10 000 premiers nombres premiers.
Modifier: j'ai oublié que cela contient la bibliothèque de mathématiques ,si vous êtes sur windows ou visual studio que ce devrait être bien, mais sur linux, vous devez compiler le code en utilisant-LM argument ou le code ne peut 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;
}
utilisant le tableau.prototype.méthode 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, vous devez le mettre en œuvre.
- pour chaque nombre, obtenez la moitié de ce nombre. Par exemple: pour la vérification 21, seulement obtenir le reste en le divisant de la gamme 2-10.
- si c'est un nombre impair, diviser seulement par le nombre impair, et vice versa. Comme pour 21, divisez avec 3, 5, 7, 9 seulement.
la méthode la plus efficace que j'ai utilisée jusqu'à présent.
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();
}
}
}