Programme pour trouver les nombres premiers

Vous pouvez le faire plus rapidement à l'aide d'un presque optimale section de première instance de tamis dans une (longue) ligne comme ceci:

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

Le rapprochement formule pour le nombre de nombres premiers utilisée ici est π(x) < 1.26 x /ln(x). Nous avons seulement besoin de tester par les nombres premiers ne sont pas plus grand que x = sqrt(num).

Noter que le crible d'Eratosthène a beaucoup plus de temps d'exécution de la complexité de la section de première instance (devrait fonctionner beaucoup plus rapidement pour un plus grand num valeurs, lorsqu'elles sont correctement mises en œuvre).

Vous avez uniquement besoin de vérifier impair de diviseurs jusqu'à la racine carrée de ce nombre. En d'autres termes, votre boucle interne doit commencer:

for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }

Vous pouvez également sortir de la fonction dès que vous trouvez le nombre n'est pas premier, vous n'avez pas besoin de vérifier plus de diviseurs (je vois que vous êtes déjà ce que!).

Cela ne fonctionnera que si le nombre est plus grand que deux.

Pas Sqrt

Vous pouvez éviter la Sqrt ensemble en conservant une somme en cours d'exécution. Par exemple:

int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}

C'est parce que la somme des chiffres 1+(3+5)+(7+9) vous donnera une séquence de petits carrés (1,9,25 etc). Et donc j représente la racine carrée de square_sum. Aussi longtemps que square_sum est à moins de i puis j est inférieur à la racine carrée.

Première étape: écrire une extension de la méthode pour savoir si une entrée est le premier

public static bool isPrime(this int number ) {

    for (int i = 2; i < number; i++) { 
        if (number % i == 0) { 
            return false; 
        } 
    }

    return true;   
}

2 étape: écrire la méthode qui vous permettra d'imprimer tous les nombres premiers entre 0 et le nombre d'entrée

public static void getAllPrimes(int number)
{
    for (int i = 0; i < number; i++)
    {
        if (i.isPrime()) Console.WriteLine(i);
    }
}

EDIT_ADD: Si Ness est vrai que la question est juste à la sortie d'un flux continu de nombres premiers pour aussi longtemps que le programme est exécuté (en appuyant sur Pause/Pause pour mettre en pause et une touche pour démarrer à nouveau) sans beaucoup d'espoir de tous arriver à ce plafond, puis le code doit être écrit sans limite d'argument et un contrôle de portée de la "vrai" pour la première " je " pour la boucle. D'autre part, si la question voulait réellement imprimer les nombres premiers jusqu'à une limite, alors le code suivant va faire le travail beaucoup plus efficacement au moyen de la Division de première instance uniquement pour les nombres impairs, avec l'avantage qu'il n'utilise pas de mémoire du tout (il pourrait également être converti en une boucle continue comme ci-dessus):

static void primesttt(ulong top_number) {
  Console.WriteLine("Prime:  2");
  for (var i = 3UL; i <= top_number; i += 2) {
    var isPrime = true;
    for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
      if (i % j == 0)  {
        isPrime = false;
        break;
      }
    }
    if (isPrime) Console.WriteLine("Prime:  {0} ", i);
  }
}

D'abord, la question de code ne produit aucune sortie à cause de ce son en boucle les variables sont des nombres entiers et la limite de l'essai est un énorme entier long, ce qui signifie qu'il est impossible pour la boucle de façon à atteindre la limite de produire une boucle interne ÉDITÉ: lequel la variable "j' boucle de retour autour de nombres négatifs; lorsque le 'j' variable revient environ à -1, l'essai numéro échoue le test d'amorçage, parce que tous les nombres sont divisibles par -1 END_EDIT. Même si cela a été corrigée, la question de code produit très lente sortie car il est lié à faire en 64 bits divisions de très grandes quantités de nombres composés (tous les numéros plus le bizarre composites) par l'ensemble de la gamme des nombres jusqu'à que nombre supérieur de dix élevé à la seizième puissance pour chaque premier qui il peut éventuellement produire. Le code ci-dessus fonctionne, car elle limite le calcul uniquement les nombres impairs et seulement modulo divisions jusqu'à la racine carrée du nombre actuel d'être testé.

Cela prend une heure pour afficher les nombres premiers jusqu'à un milliard de dollars, de sorte que l'on peut imaginer la quantité de temps qu'il faudrait pour afficher tous les nombres premiers inférieurs à dix mille milliards de dollars (10 élevé à la seizième puissance), d'autant que le calcul devient plus lent, avec une augmentation de la distance. END_EDIT_ADD

Bien que l'un liner (genre de) réponse par @SLaks à l'aide de Linq fonctionnement, il n'est pas vraiment le Crible d'Eratosthène que c'est juste une unoptimised version de Division De Première Instance, unoptimised en ce qu'elle n'élimine pas l'impair de nombres premiers, ne démarre pas à la place du trouvé de la base de premier, et de ne pas arrêter l'abattage pour la base de nombres premiers plus grand que la racine carrée du nombre supérieur à tamis. Il est également très lent en raison de multiples imbriqués l'énumération des opérations.

Il est en fait un abus de Linq méthode des Agrégats et de ne pas utiliser efficacement la première des deux Linq Gamme de produit. Il peut devenir un optimisée de la Division de première instance avec moins dénombrement de frais généraux comme suit:

static IEnumerable<int> primes(uint top_number) {
  var cullbf = Enumerable.Range(2, (int)top_number).ToList();
  for (int i = 0; i < cullbf.Count; i++) {
    var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
    cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
  } return cullbf; }

qui s'exécute plusieurs fois plus rapide que la SLaks réponse. Cependant, il est encore lent et de mémoire intensive en raison de la Liste de la génération et de la multiplicité des énumérations ainsi que les multiples fracture (implicite par le modulo) opérations.

La suite Crible d'Eratosthène mise en œuvre s'exécute environ 30 fois plus rapide et prend beaucoup moins de mémoire qu'il utilise seulement un peu de la représentation par nombre tamisé et les limites de son énumération à la finale itérateur sortie de la séquence, comme bien d'avoir des optimisations de traiter seulement bizarre composites, et seulement l'abattage de la carrés de la base de nombres premiers pour la base de nombres premiers inférieurs à la racine carrée du nombre maximal, comme suit:

static IEnumerable<uint> primes(uint top_number) {
  if (top_number < 2u) yield break;
  yield return 2u; if (top_number < 3u) yield break;
  var BFLMT = (top_number - 3u) / 2u;
  var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
  var buf = new BitArray((int)BFLMT + 1,true);
  for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
      var p = 3u + i + i; if (i <= SQRTLMT) {
        for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
          buf[(int)j] = false; } yield return p; } }

Le code ci-dessus calcule tous les nombres premiers inférieurs à dix millions de gamme dans environ 77 millisecondes sur un processeur Intel i7-2700K (3.5 GHz).

L'une des deux méthodes statiques peuvent être appelés et testé avec les instructions à l'aide et à la statique Principale méthode comme suit:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

static void Main(string[] args) {
  Console.WriteLine("This program generates prime sequences.\r\n");

  var n = 10000000u;

  var elpsd = -DateTime.Now.Ticks;

  var count = 0; var lastp = 0u;
  foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }

  elpsd += DateTime.Now.Ticks;
  Console.WriteLine(
    "{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
    count, n, lastp,elpsd / 10000);

  Console.Write("\r\nPress any key to exit:");
  Console.ReadKey(true);
  Console.WriteLine();
}

qui affichera le nombre de nombres premiers dans l'ordre jusqu'à la limite, le dernier premier trouvé, et le temps consacré à l'énumération de loin.

EDIT_ADD: Toutefois, afin de produire une énumération du nombre de nombres premiers inférieurs à dix mille milliards de dollars (dix à la seizième puissance) que la question demande, une segmentation paginée approche de l'utilisation de multi-core de traitement est nécessaire, mais même avec le C++ et le très hautement optimisé PrimeSieve, cela nécessiterait quelque chose de plus de 400 heures à produire le nombre de nombres premiers trouvés, et des dizaines de fois que le long de tous les énumérer ainsi, sur une année pour faire ce que la question se pose. Faire à l'aide de l'onu-optimisé Division de première instance de l'algorithme tenté, il va prendre super éons et un très très long moment, même à l'aide d'un optimisée de la section de première instance de l'algorithme, comme dans quelque chose comme dix à la deux millionième années de pouvoir (c'est deux millions de zéros ans!!!!!).

Il n'est pas étonnant que son ordinateur de bureau à juste assis et a décroché quand il a essayé!!!! S'il avait essayé une petite plage comme un million de dollars, il aurait constaté qu'il prend dans la gamme de secondes de mise en œuvre.

Les solutions que je poste ici ne pas le couper plus que même le dernier Crible d'Eratosthène on aura besoin d'environ 640 Téraoctets de mémoire pour cette gamme.

C'est pourquoi seule une page d'approche segmentée comme celui de PrimeSieve peut gérer ce genre de problème pour la plage comme spécifié à tous, et même ce qui nécessite un temps très long, comme dans les semaines à ans, sauf si l'on a accès à un super-ordinateur avec des centaines de milliers de cœurs. END_EDIT_ADD

Une ligne de code en C# :-

Console.WriteLine(String.Join(Environment.NewLine, 
    Enumerable.Range(2, 300)
        .Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
        .All(nn => n % nn != 0)).ToArray()));                                    

ExchangeCore Forums avoir une bonne console application énumérés qui ressemble à écrire trouvé les nombres premiers dans un fichier, il semble que vous pouvez également utiliser ce même fichier en tant que point de départ de sorte que vous n'avez pas à redémarrer trouver des nombres premiers de 2 et ils fournissent le téléchargement de ce fichier avec tous trouvé les nombres premiers jusqu'à 100 millions de dollars de sorte qu'il serait un bon début.

L'algorithme sur la page prend également quelques raccourcis (numéros impairs et vérifie seulement jusqu'à la racine carré) ce qui le rend extrêmement efficace et il vous permettra de calculer les nombres longs.

Pour être tout à fait franc, certaines des solutions proposées sont vraiment très lent, et, par conséquent, sont de mauvais conseils. Pour le test d'un seul numéro pour être le premier vous avez besoin de quelques divisant/opérateur modulo, mais pour le calcul d'une plage que vous n'avez pas à.

Fondamentalement, il suffit d'exclure les nombres qui sont des multiples de plus tôt trouvé les nombres premiers, comme le sont, par définition, pas de nombres premiers eux-mêmes.

Je ne vais pas donner la pleine mise en œuvre, que ce serait facile, c'est l'approche en pseudo code. (Sur ma machine, la mise en œuvre effective calcule tous les nombres premiers dans un Système.Int32 (2 milliards) dans un délai de 8 secondes.

public IEnumerable<long> GetPrimes(long max)
{
    //we safe the result set in an array of bytes.
    var buffer = new byte[long >> 4];
    //1 is not a prime.
    buffer[0] = 1;

    var iMax = (long)Math.Sqrt(max);

    for(long i = 3; i <= iMax; i +=2 )
    {
        //find the index in the buffer
        var index = i >> 4;
        //find the bit of the buffer.
        var bit = (i >> 1) & 7;

        //A not set bit means: prime
        if((buffer[index] & (1 << bit)) == 0)
        {
            var step = i << 2;
            while(step < max)
            {
                //find position in the buffer to write bits that represent number that are not prime.
            }
        }
        //2 is not in the buffer.
        yield return 2;

        //loop through buffer and yield return odd primes too.
    }
}

La solution nécessite une bonne compréhension des opérations bit à bit. Mais il des moyens, et des moyens plus rapides. Vous pouvez également sûr le résultat le résultat sur le disque, si vous en avez besoin pour une utilisation ultérieure. Le résultat de 17 * 10^9 numéros peuvent être safed avec 1 GO, et le calcul de l'ensemble des résultats prend environ 2 minutes max.

Très similaire à partir d'un exercice pour mettre en œuvre Crible d'Eratosthène en C#:

public class PrimeFinder
{
    readonly List<long> _primes = new List<long>();

    public PrimeFinder(long seed)
    {
        CalcPrimes(seed);
    }

    public List<long> Primes { get { return _primes; } }

    private void CalcPrimes(long maxValue)
    {
        for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
        {
            if (IsPrime(checkValue))
            {
                _primes.Add(checkValue);
            }
        }
    }

    private bool IsPrime(long checkValue)
    {
        bool isPrime = true;

        foreach (long prime in _primes)
        {
            if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
            {
                isPrime = false;
                break;
            }
        }
        return isPrime;
    }
}

    public static void Main()
{  
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();          
}

U peut utiliser la normale nombre premier concept doit seulement deux facteurs (l'un et de lui-même).
Afin de faire ceci,de façon facile

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}

C'est le moyen le plus rapide pour calculer les nombres premiers en C#.

   void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long  value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{             
if (number % i == 0)
{
//MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}

Il y a quelques très optimale des moyens à mettre en œuvre l'algorithme. Mais si vous ne savez pas beaucoup au sujet de maths et il vous suffit de suivre la définition du premier que de l'exigence:
un nombre qui n'est divisible que par 1 et par lui-même (et rien d'autre), voici une technique simple pour la compréhension du code pour les nombres positifs.

public bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}

Puisque chaque nombre est divisible par 1 et par lui-même, nous avons commencer à vérifier à partir de 2 jusqu'à ce que le nombre immédiatement avant de lui-même. C'est le raisonnement de base.