La plupart du code efficace pour les 10000 premiers nombres premiers?

voix
49

Je veux imprimer les 10000 premiers nombres premiers. Quelqu'un peut-il me donner le code le plus efficace pour cela? clarifications:

  1. Peu importe si votre code est inefficace pour n> 10000.
  2. La taille du code n'a pas d'importance.
  3. Vous ne pouvez pas coder en dur les valeurs de quelque manière.
Créé 03/08/2008 à 06:45
source utilisateur
Dans d'autres langues...                            


28 réponses

voix
41

Le Crible d'Atkin est probablement ce que vous cherchez, son temps de fonctionnement limite supérieure est O (N / log log N).

Si vous exécutez uniquement les numéros 1 et plus 1 moins que les multiples de 6, il pourrait être encore plus rapide, comme tous les nombres premiers 3 ci - dessus sont loin de 1 un multiple de six. Ressource pour ma déclaration

Créé 03/08/2008 à 07:03
source utilisateur

voix
35

Je recommande un tamis, soit le Crible d'Eratosthène ou Crible d'Atkin.

Le tamis ou Eratosthène est probablement la méthode la plus intuitive de trouver une liste des nombres premiers. Fondamentalement, vous:

  1. Notez une liste de numéros de 2 à quelque limite que vous voulez, disons 1000.
  2. Prenez le premier numéro qui ne raya (pour la première itération est ce 2) et rayez tous les multiples de ce nombre dans la liste.
  3. Répétez l'étape 2 jusqu'à la fin de la liste. Tous les chiffres qui ne sont pas biffé sont premiers.

De toute évidence, il y a un certain nombre d'optimisations qui peut être fait pour faire ce travail d'algorithme plus rapide, mais cela est l'idée de base.

Le tamis de Atkin utilise une approche similaire, mais malheureusement, je ne sais pas assez pour vous l'expliquer. Mais je sais que je l'algorithme prend 8 secondes lié à comprendre tous les nombres premiers jusqu'à 1000000000 sur un ancien Pentium II-350

Crible d'Eratosthène Source Code: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Crible d'Atkin Source Code: http://cr.yp.to/primegen.html

Créé 06/08/2008 à 00:49
source utilisateur

voix
17

Ce n'est pas strictement contre la restriction de hardcoding, mais est terriblement proche. Pourquoi ne pas télécharger cette liste et programatically l'imprimer, à la place?

http://primes.utm.edu/lists/small/10000.txt

Créé 31/08/2008 à 23:20
source utilisateur

voix
11

GateKiller , que diriez - vous d' ajouter un breakque ifdans la foreachboucle? 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 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 + " ");
    }
}
Créé 27/08/2008 à 21:26
source utilisateur

voix
9

Dans Haskell, nous pouvons écrire presque mot pour mot la définition mathématique du tamis d'Eratosthène, « nombres premiers sont des nombres naturels supérieurs à 1 sans nombres composés, où 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 quasi-instantanée.

Les références:


Le code ci - dessus est facilement peaufiné en travaillant 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 beaucoup améliorée (à peu près un journal facteur ci - dessus optimal) par pliage dans une structure arborescente, et la complexité de l' espace est considérablement améliorée par la production de nombres premiers en plusieurs étapes , en

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é que par juxtaposition, (:)est un contre opérateur pour les listes, et (.)est un opérateur de composition fonctionnelle: (f . g) x = (\y-> f (g y)) x = f (g x)).

Créé 24/04/2012 à 17:30
source utilisateur

voix
9

@ Matt: log (log (10000)) est ~ 2

De l'article wikipedia (que vous citiez) Crible d'Atkin :

Ce tamis calcule les nombres premiers à N en utilisant des O(N/log log N)opérations avec seulement N 1/2 + O (1) bits de mémoire. C'est un peu mieux que le tamis d'Eratosthène qui utilise des O(N) opérations et O (N 1/2 (log log N) / log N) bits de mémoire (AOL Atkin, DJ Bernstein, 2004) . Ces complexités de calcul asymptotique comprennent des optimisations simples, telles que la roue factorisation et division du calcul à des blocs plus petits.

Compte tenu de la complexité de calcul asymptotique 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) qui algorithme si elle est appliquée sera plus rapide.

Achim Flammenkamp a écrit dans Le Crible d'Eratosthène :

cité par:

@ num1

Pour des intervalles plus grands environ 10 ^ 9, sûrement pour ceux> 10 ^ 10, la Sieve d'Eratosthène est surclassé par le Crible d'Atkins et Bernstein qui utilise des formes quadratiques binaires irréductibles. Voir leur papier pour des informations de fond ainsi que le paragraphe 5 du doctorat de W. Galway thèse.

Par conséquent , pour 10_000Sieve d'Eratosthène peut être plus rapide alors Crible d'Atkin.

Pour répondre à OP le code est prime_sieve.c (cité par num1)

Créé 06/10/2008 à 21:03
source utilisateur

voix
7

En utilisant GMP, on pourrait écrire:

#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 est exécuté comme suit:

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

Calcul de nombres premiers sur 1.000.000 le même ordinateur portable:

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP est fortement optimisé pour ce genre de chose. À moins que vous voulez vraiment comprendre les algorithmes en écrivant votre propre, vous seriez conseillé d'utiliser libgmp sous C.

Créé 29/08/2008 à 08:06
source utilisateur

voix
4

J'ai un code adapté trouvé sur le CodeProject pour créer les éléments suivants:

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 + " ");
    }
}

Test sur mon serveur ASP.NET a pris la rountine environ 1 minute à courir.

Créé 05/08/2008 à 20:55
source utilisateur

voix
4

Pas efficace du tout, mais vous pouvez utiliser une expression régulière pour tester les nombres premiers.

/^1?$|^(11+?)\1+$/

Ce test si, pour une chaîne constituée de k « 1» s, k est pas premier ( à savoir si la chaîne se compose d'un « 1» ou un certain nombre de « 1» s qui peut être exprimé en n produit -aire).

Créé 03/08/2008 à 19:52
source utilisateur

voix
3

Voici un Sieve d'Eratosthène que je l'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
}
Créé 07/09/2009 à 19:52
source utilisateur

voix
3

Crible d'Eratosthène est la voie à suivre, en raison de sa simplicité et de rapidité. 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;
}

Le temps CPU pour trouver des nombres premiers (sur Pentium Dual Core E2140 cadencé à 1,6 GHz, en utilisant un seul coeur)

~ 4 s pour lim = 100000000

Créé 21/08/2008 à 00:45
source utilisateur

voix
2

L' algorithme de tamis deque mentionné par BenGoldberg mérite un examen plus approfondi, non seulement parce qu'il est très élégant mais aussi parce qu'il peut parfois être utile dans la pratique (contrairement à la Crible d'Atkin, qui est un exercice purement académique).

L'idée de base derrière l'algorithme de tamis deque est d'utiliser un petit tamis coulissant qui est juste assez grande pour contenir au moins un multiple distinct pour chacun des facteurs premiers en « actifs » - à savoir les nombres premiers dont le carré ne dépasse pas le nombre le plus bas actuellement représentée par le tamis mobile. Une autre différence à l'état de l'environnement est que les magasins de tamis deque les facteurs réels dans les fentes des composites, non booléens.

L'algorithme étend la taille de la fenêtre de tamis au besoin, ce qui assez même performance sur une large gamme jusqu'à ce que le tamis commence dépassant la capacité du cache L1 de la CPU sensiblement. Le dernier premier qui correspond entièrement est 25237523 (le premier de 1,579,791st), ce qui donne une idée approximative approximative pour la plage de fonctionnement raisonnable de l'algorithme.

L'algorithme est assez simple et robuste, et il a même des performances sur une gamme beaucoup plus large qu'une Sieve d'Eratosthène non segmenté. Ce dernier est beaucoup plus rapide aussi longtemps son tamis s'inscrit pleinement dans le cache, soit jusqu'à 2 ^ 16 pour une cote seulement tamis avec un octet de taille bools. Ensuite, ses performances diminue de plus en plus, bien qu'il reste toujours beaucoup plus rapide que le 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 tamis deque en C #, parce que je trouve cette langue - malgré ses nombreux défauts - beaucoup plus pratique pour les algorithmes de prototypage et d' expérimentation que le suprêmement lourd et pédant C ++. (Sidenote: J'utilise le libre LINQPad qui permet de plonger en plein, sans que tous les salissant avec la mise en place des projets, makefile, répertoires ou autres joyeusetés, et il me donne le même degré d'interactivité comme une invite de python).

C # ne dispose pas d' un type explicite deque mais la plaine List<int>fonctionne assez bien pour démontrer l'algorithme.

Note: cette version n'utilise pas deque pour les nombres premiers, parce qu'il n'a tout simplement pas de sens pour faire sauter sqrt (n) de nombres premiers n. A quoi bon serait-il de 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 meilleure façon de comprendre l'algorithme est de l'imaginer comme segmentée spécial d'Eratosthène avec Sieve une taille de segment de 1, accompagné d'une zone de débordement où les nombres premiers viennent se reposer quand ils tirent sur la fin du segment. Sauf que la cellule unique du segment (aka sieve[0]) a déjà été tamisé quand on arrive à, car il se est écrasé alors qu'il faisait partie de la zone de débordement.

Le nombre qui est représenté par sieve[0]se tient à sieve_base, bien sieve_frontou window_baseserait également un bon nom qui permettent d'établir des parallèles au code de Ben ou implémentations de tamis segmentés / fenêtré.

Si sieve[0]contient une valeur non nulle alors que la valeur est un facteur sieve_base, qui peut donc être reconnue comme composite. Puisque la cellule 0 est un multiple de ce facteur , il est facile de calculer son saut suivant, ce qui est tout simplement 0 plus ce facteur. Si cette cellule est déjà occupée par un autre facteur nous ajoutons simplement le facteur nouveau, et ainsi de suite jusqu'à ce qu'on trouve un multiple du facteur où aucun autre facteur est actuellement stationné (extension du tamis si nécessaire). Cela signifie également qu'il n'y a pas besoin de stocker les décalages de travail actuelles des différents nombres premiers d'un segment à l'autre, comme dans un tamis segmenté normal. Chaque fois que nous trouvons un facteur sieve[0], son courant de travail offset est 0.

Le premier courant entre en jeu de la manière suivante. Un premier ne peut se mettre à jour après sa propre apparition dans le flux (quand il a été détecté comme premier, car non marqué par un facteur), et il restera valable jusqu'au moment précis où sieve[0]atteint sa place. Tous les multiples inférieurs de ce premier doivent avoir été rayées en raison des activités de petits nombres premiers, comme dans un état de l' environnement normal. Mais aucun des nombres premiers plus petits peut frapper de la place, puisque le seul facteur de la place est le premier lui - même et il est pas encore en circulation à ce moment. Cela explique les mesures prises par l'algorithme dans le cas sieve_base == current_prime_squared( ce qui implique sieve[0] == 0, par la voie).

Maintenant , le cas sieve[0] == 0 && sieve_base < current_prime_squaredest facile à expliquer: cela signifie que sieve_basene peut pas être un multiple de l' un des nombres premiers plus petits que le premier courant, ou bien il aurait été marqué comme composite. Je ne peux pas être un multiple supérieur du premier courant soit, puisque sa valeur est inférieure à la place du premier courant. Par conséquent , il doit être un nouveau premier.

L'algorithme est évidemment inspiré par le Crible d'Ératosthène, mais aussi de toute évidence, il est très différent. Le Crible d'Eratosthène tire sa vitesse supérieure de la simplicité de ses opérations élémentaires: un ajout unique d'index et un magasin pour chaque étape de l'opération est tout ce qu'il fait pendant de longues périodes de temps.

Voici un moyen simple, non segmenté d'Eratosthène que Sieve j'utilise normalement pour les nombres premiers facteur tamiser dans la gamme ushort, soit jusqu'à 2 ^ 16. Pour ce poste , je l' ai modifié à travailler au - delà de 2 ^ 16 en substituant intà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;
}

Lorsque tamiser le premier 10000 nombres premiers un cache L1 typique de 32 Kiocte sera dépassé, mais la fonction est encore très rapide (fraction de 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, car il fait toujours le plus court tronçon possible des passages à niveau au large dans une rangée (exactement un seul passage à pied, après avoir sauté tous les multiples qui ont biffé déjà).

Remarque: le code C # utilise au intlieu de uintcar de nouveaux compilateurs ont l'habitude de générer un code de qualité inférieure pour uint, probablement afin de pousser les gens vers des entiers signés ... Dans la version C ++ du code au- dessus je unsignedtout au long, naturellement; l'indice de référence devait être en C ++ parce que je voulais être basé sur un type deque soi - disant adéquat ( std::deque<unsigned>, il n'y avait pas de gain de performance de l' utilisation unsigned short). Voici les chiffres pour 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

Remarque: les temps C # sont assez bien le double exactement les timings C ++, ce qui est assez bon pour C # et la montre qui List<int>est pas en reste , même si abusé comme deque.

Le code de tamis simple, souffle encore le deque hors de l'eau, même si elle fonctionne déjà au-delà de sa plage de fonctionnement normale (taille du cache L1 dépassé de 50%, avec raclée cache opératrices). La partie dominante est ici la lecture des nombres premiers tamisées, et ce n'est pas affectée autant par le problème du cache. En tout cas, la fonction a été conçue pour tamiser les facteurs de facteurs, à savoir niveau 0 dans une hiérarchie de tamis à 3 niveaux, et généralement il doit revenir à quelques centaines de facteurs ou un faible nombre de milliers. D'où sa simplicité.

Performance pourrait être améliorée par plus d'un ordre de grandeur à l'aide d' un tamis segmenté et en optimisant le code pour extraire les nombres premiers tamisées (intensifié mod 3 et déroulé deux fois, ou mod 15 et déroulé une fois), et encore plus de performance peut être pressé hors de le code en utilisant un 16 ou 30 mod mod roue avec tous les accessoires (c. -à- plein déroulement pour tous les résidus). Quelque chose comme ça est expliqué dans ma réponse à trouver le numéro premier Premier positionné sur le Code Review, où un problème similaire a été discuté. Mais il est difficile de voir le point à améliorer les temps sous-millièmes de seconde pour une tâche unique ...

Pour mettre les choses un peu en perspective, voici les horaires du 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

En revanche, un tamis segmenté en C # avec quelques cloches et de sifflets fait le même travail en 95 ms (pas C ++ timings disponible, puisque je ne ne conteste que le code en C # pour le moment).

Les choses peuvent sembler décidément différent dans un langage interprété comme Python où chaque opération a un coût élevé et les frais généraux interprète toutes les différences naines en raison de branches prévues par rapport ou opérations sous mal prédit cycle (changement, plus) par rapport aux opérations sur plusieurs cycles (multiplication , et peut-être même division). Cela est lié à éroder l'avantage de la simplicité du Crible d'Eratosthène, et cela pourrait rendre la solution deque un peu plus attrayant.

De plus, beaucoup des horaires déclarés par d' autres répondants dans ce sujet sont probablement dominé par le temps de sortie . C'est une guerre tout à fait différent, où mon arme principale est une simple classe comme ceci:

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 l'écriture 10000 (triées) chiffres. Il est une classe statique, car il est destiné à être inclus dans le texte de codage soumissions de défi, avec un minimum de bruit et zéro frais généraux.

En général , je trouve qu'il est beaucoup plus rapide si le travail concentré est effectué sur des lots entiers, tamis qui signifie une certaine plage, puis extraire tous les nombres premiers dans un vecteur / tableau, puis faire sauter le tableau entier, puis tamisez la plage suivante et ainsi de suite, au lieu de se mêler tout ensemble. Avoir des fonctions distinctes axées sur des tâches spécifiques rend également plus facile de mélanger et assortir, il permet la réutilisation, et il facilite le développement / tests.

Créé 19/04/2016 à 17:07
source utilisateur

voix
2

en Python

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p 
Créé 22/02/2010 à 08:45
source utilisateur

voix
2

Le Sieve semble être la mauvaise réponse. Le tamis vous donne les nombres premiers jusqu'à un nombre N , et non les N premiers nombres premiers. Exécutez @Imran ou Szeto @ Andrew, et vous obtenez les nombres premiers jusqu'à N.

Le tamis peut encore être utile si vous continuez à essayer des tamis pour un nombre de plus en plus grands jusqu'à ce que vous atteignez une certaine taille de votre jeu de résultats et d'utiliser une mise en cache des chiffres déjà obtenus, mais je crois qu'il serait encore pas plus vite qu'une solution comme @ Pat .

Créé 19/06/2009 à 19:12
source utilisateur

voix
2

L' adaptation et à la suite de GateKiller , voici la version finale que je l' 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;
    }

Il est fondamentalement la même chose, mais je l'ai ajouté la « rupture sur Sqrt » suggestion et a changé certaines des variables autour de l'adapter mieux pour moi. (Je travaillais sur Euler et avait besoin du premier 10001th)

Créé 16/02/2009 à 06:17
source utilisateur

voix
1

L'utilisation d'Eratosthène Sieve, le calcul est assez rapide à comparer « connu dans le » algorithme de choix de nombres.

En utilisant pseudocode à partir de son wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ), je serai en mesure d'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.

REMARQUE : la valeur peut varier dépendent de caractéristiques du matériel.

Créé 12/05/2016 à 03:40
source utilisateur

voix
1

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 Sieve peut calculer les nombres premiers indéfiniment.

A noter également, la STL dequeprend du O(1)temps pour effectuer push_back, pop_frontet l' accès aléatoire si subscripting.

L' resizeopération prend du O(n)temps, où nest le nombre d'éléments étant ajouté. En raison de la façon dont nous utilisons cette fonction, nous pouvons traiter c'est une petite constante.

Le corps de la whileboucle my_insertest exécutée O(log log n)fois, où nest égal à la variable maybe_prime. En effet , l'expression de la condition de la whileévaluera true une fois pour chaque facteur premier maybe_prime. Voir « Fonction Diviseur » sur Wikipedia.

Par le nombre multiplication de fois my_insertest appelé, montre qu'il devrait prendre le O(n log log n)temps de la liste des nnombres premiers ... ce qui est, sans surprise, la complexité de temps que le Crible d'Eratosthène est censé avoir.

Cependant, alors que ce code est efficace, ce n'est pas le plus efficace ... Je suggère fortement d' utiliser une bibliothèque spécialisée pour la génération de nombres premiers, comme primesieve . Toute solution, bien optimisé vraiment efficace, prendra plus de code que quiconque veut entrer dans Stackoverflow.

Créé 16/04/2016 à 18:33
source utilisateur

voix
1

Le code suivant Mathcad calculé le premier million de nombres premiers en moins de 3 minutes.

Gardez à l'esprit que ce serait d'utiliser à virgule flottante double pour tous les chiffres et est essentiellement interprété. J'espère que la syntaxe est claire.

entrez la description d'image ici

Créé 02/03/2014 à 02:15
source utilisateur

voix
1

Voici mon code VB 2008, qui trouve tous les nombres premiers <10.000.000 en 1 min 27 sec sur mon ordinateur portable de travail. Il saute même nombre et ne recherche que les nombres premiers qui sont <sqrt du numéro de test. Il est seulement conçu pour trouver des nombres premiers de 0 à une valeur Sentinal.

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
Créé 11/03/2011 à 03:25
source utilisateur

voix
0

Puisque vous voulez 10000 premiers nombres premiers que, plutôt que de coder l'algorithme complexe je suggère 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 appel est premier que vous en avez besoin

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}
Créé 16/11/2018 à 05:34
source utilisateur

voix
0

Je peux vous donner quelques conseils, vous devez le mettre en œuvre.

  1. Pour chaque numéro, obtenir la moitié de ce nombre. Par exemple, pour le contrôle de 21, seulement obtenir le reste en le divisant de la gamme 2-10.
  2. Si son un nombre impair, que diviser par nombre impair, et vice versa. Tel que, par 21, diviser par 3, 5, 7, 9 seulement.

La méthode la plus efficace que je suis arrivé à ce jour.

Créé 29/07/2018 à 19:25
source utilisateur

voix
0

En utilisant 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
Créé 09/06/2018 à 21:49
source utilisateur

voix
0

Voici le code que je 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;
}
Créé 20/01/2018 à 15:50
source utilisateur

voix
0

Voici mon code qui trouve 10.000 premiers nombres premiers en 0,049655 sec sur mon ordinateur portable, premier 1.000.000 nombres premiers en moins de 6 secondes et la première 2.000.000 en 15 secondes
une petite explication. Cette méthode utilise 2 techniques pour trouver nombre premier

  1. tout d'abord un nombre non premier est un composite de multiples de nombres premiers alors ce test de code en divisant le nombre d'essai par de plus petits nombres premiers à la place d'un nombre quelconque, ce qui diminue le calcul par atleast 10 fois pour un nombre à 4 chiffres et encore plus pour un plus grand nombre
  2. d'autre part, en plus de la division par le premier, il se divise uniquement par des nombres premiers qui sont inférieures ou égales à la racine du nombre étant testé qui réduit encore les calculs beaucoup, cela fonctionne parce que tout chiffre qui est supérieur à la racine du nombre aura un numéro de contrepartie que doit être inférieure à la racine du nombre, mais étant donné que nous avons testé tous les nombres inférieurs à la racine déjà, donc on n'a pas besoin de déranger avec un nombre supérieur à la racine du nombre testé.

Exemple de sortie pour le premier nombre premier 10 000
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

Voici le code en langage C, Entrez 1 et 10 000 pour imprimer les 10.000 premiers nombres premiers.
Edit: J'ai oublié cette bibliothèque contient les mathématiques, si vous êtes sur Windows ou visual studio que cela devrait être bien , mais sur linux , vous devez compiler le code en utilisant l' argument -lm 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);
}
Créé 06/05/2017 à 11:48
source utilisateur

voix
0

Je travaille sur les nombres premiers de trouver pour environ un an. Ce que j'ai trouvé être 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 se rendre à 2147483629 à partir de 2.

Créé 14/08/2016 à 00:20
source utilisateur

voix
0

Je passe un certain temps à écrire un programme de calcul beaucoup de nombres premiers, ce qui est le code que je suis habitué à calculer un fichier texte contenant les premiers 1.000.000.000 nombres premiers. Il 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 processeur 64 bits , car les calculs sont des entiers de 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);
        }
    }
}
Créé 23/04/2012 à 20:46
source utilisateur

voix
0

Je l' ai écrit en Python, comme je viens d' apprendre a commencé, et il fonctionne parfaitement bien. Le premier 10.000ème générer par ce code comme même que mentionné dans http://primes.utm.edu/lists/small/10000.txt . Pour vérifier si nest premier ou non, diviser npar le nombre de 2à sqrt(n). Si l' une de cette gamme de numéro parfaitement divise nalors il 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))
Créé 27/12/2010 à 18:37
source utilisateur

voix
-1
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();
        }
    }
}
Créé 08/05/2012 à 05:15
source utilisateur

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more