Programme pour trouver des nombres premiers
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je veux trouver le nombre premier entre 0 et une variable longue mais je ne suis pas en mesure d'obtenir une sortie.
Le programme est
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
Quelqu'un peut-il me aider et trouver ce qui est l'erreur possible dans le programme?
La solution
Vous pouvez le faire plus rapidement en utilisant un presque optimale tamis de la division d'essai dans une ligne (long) 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;
}
);
La formule d'approximation pour le nombre de nombres premiers est utilisé ici π(x) < 1.26 x / ln(x) . Nous ne devons tester par les nombres premiers pas plus grand que x = sqrt(num) .
Notez que le de Eratosthène a beaucoup mieux la complexité de l'exécution de la division d'essai (devrait fonctionner beaucoup plus rapide pour les plus num valeurs, lorsqu'il est correctement mis en œuvre).
Autres conseils
Essayez ceci:
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
Il vous suffit de vérifier impairs jusqu'à diviseurs la racine carrée du 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 trouverez le nombre n'est pas premier, vous n'avez pas besoin de vérifier les plus diviseurs (faisant, je vois que vous déjà!).
Cela ne fonctionnera que si num est plus grand que deux.
Non Sqrt
Vous pouvez éviter sqrt tout en gardant une somme courante. Par exemple:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
En effet, la somme des nombres 1+ (3 + 5) + (7 + 9) vous donnera une séquence de carrés impairs (1,9,25 etc.). Et donc j représente la racine carrée de square_sum. Tant que square_sum est inférieure à i alors j est inférieure à la racine carrée.
Les gens ont mentionné deux des blocs de construction vers le faire efficacement, mais personne ne vraiment mettre les morceaux ensemble. Les de Ératosthène est un bon début, mais il vous tomberez de mémoire < em> long avant d'atteindre la limite que vous avez défini. Cela ne veut pas dire qu'il est inutile que - lorsque vous faites votre boucle, ce qui vous intéresse vraiment sont les diviseurs premiers. En tant que tel, vous pouvez commencer par utiliser le tamis pour créer une base de diviseurs premiers, puis utilisez ceux dans la boucle pour tester les numéros pour la primauté.
Lorsque vous écrivez la boucle, cependant, vous ne voulez vraiment pas nous sqrt (i) dans la condition de la boucle comme deux réponses ont suggéré. Vous et je sais que la sqrt est une fonction « pure » qui donne toujours la même réponse si on leur donne le même paramètre d'entrée. Malheureusement, le compilateur ne sait pas que, si utiliser quelque chose comme « <= Math.sqrt (x) » dans la condition de la boucle, il va re-calculer la racine carrée du nombre chaque itération de la boucle.
Vous pouvez éviter que deux façons différentes. Vous pouvez pré-calculer la racine carrée avant la boucle, et utiliser la valeur pré-calculée dans la condition de la boucle, ou vous pouvez travailler dans l'autre sens, et changer i<Math.sqrt(x) à i*i<x. Personnellement, je précalculer la racine carrée bien - je pense qu'il est plus clair et probablement un peu plus vite - mais cela dépend du nombre d'itérations de la boucle (le i*i signifie qu'il fait encore une multiplication dans la boucle). Avec seulement quelques itérations, i*i sera généralement plus rapide. Avec suffisamment d'itérations, la perte de i*i chaque itération l'emporte sur le temps d'exécution sqrt une fois en dehors de la boucle.
C'est probablement suffisant pour la taille des chiffres que vous avez affaire - une limite de 15 chiffres signifie la racine carrée est 7 ou 8 chiffres, ce qui correspond à une quantité assez raisonnable de la mémoire. D'autre part, si vous voulez traiter avec des chiffres dans cette gamme beaucoup, vous voudrez peut-être regarder quelques-uns des algorithmes prime de contrôle plus sophistiqués, tels que les algorithmes de Pollard ou de Brent . Ceux-ci sont plus complexes (pour le moins) mais beaucoup plus rapide pour un grand nombre.
Il existe d'autres algorithmes pour un nombre encore plus grand ( quadratique tamis , numéro général tamis sur le terrain), mais nous n'entrer dans eux pour le moment - ils sont beaucoup plus complexes et vraiment utile pour faire face aux chiffres très gros (le GNFS commence à être utile dans la gamme 100+ de chiffres).
Première étape: écrire une méthode d'extension pour savoir si une entrée est premier
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
Étape 2: écrire la méthode qui permet d'imprimer tous les nombres premiers qui sont entre 0 et l'entrée du numéro
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
Il peut être juste mon avis, mais il y a une autre grave erreur dans votre programme (annulation de la donnée « nombre premier » question, qui a été soigneusement répondu).
Comme le reste des intervenants, je suppose que c'est des devoirs, que vous voulez devenir indique un développeur (probablement).
Vous devez apprendre à compartimenter votre code. Ce n'est pas quelque chose que vous aurez toujours besoin de faire dans un projet, mais il est bon de savoir comment le faire.
Votre méthode prime_num (longue num) pourrait se tenir mieux, le nom plus descriptif. Et si on est censé trouver tous les nombres premiers inférieur à un nombre donné, il doit les retourner comme une liste. Cela rend plus facile à séparer votre écran et votre fonctionnalité.
Si simplement renvoyé un IList contenant des nombres premiers, vous pouvez ensuite les afficher dans votre fonction principale (peut-être appeler une autre fonction en dehors de les imprimer assez) ou les utiliser dans d'autres calculs en bas de la ligne.
meilleure recommandation pour vous mon est de faire quelque chose comme ceci:
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
Même si vous finissez par travailler dans un endroit où speration comme celui-ci n'est pas nécessaire, il est bon de savoir comment le faire.
Edit_add: Si Will Ness est exact que le but de 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 faire une pause et une touche pour démarrer à nouveau) sans espoir sérieux de chaque arriver à cette limite supérieure, le code doit être écrit sans argument de limite supérieure et une vérification de la gamme « true » pour la première « i » pour la boucle. D'autre part, si la question voulait réellement imprimer les nombres premiers jusqu'à une limite, puis le code suivant fera le travail beaucoup plus efficacement à l'aide Section de première instance que pour les nombres impairs, avec l'avantage qu'il n'utilise pas de mémoire du tout (il peut également être converti en une boucle continue selon la 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);
}
}
Tout d'abord, le code question ne produit aucune sortie en raison de que ses variables de boucle sont des nombres entiers et la limite testée est un énorme entier long, ce qui signifie qu'il est impossible pour la boucle d'atteindre la limite produisant une boucle intérieure ÉDITÉ: de sorte que les boucles « j » variables en arrière autour des nombres négatifs; lorsque la variable « j » revient autour de -1, le nombre testé échoue au test premier car tous les nombres sont divisibles par -1 END_EDIT . Même si cela a été corrigé, le code question produit une sortie très lente, car elle se lie par faire les divisions 64 bits de très grandes quantités de nombres composés (tous les nombres pairs plus les composites impairs) par l'ensemble des nombres jusqu'à ce haut nombre de dix élevé à la puissance seizième pour chaque prime qu'il peut éventuellement produire. Le code ci-dessus fonctionne, car il limite le calcul uniquement les nombres impairs et ne fait que les divisions modulo jusqu'à la racine carrée du nombre actuel testé .
Cela prend une heure pour afficher les nombres premiers jusqu'à un milliard, donc on peut imaginer la quantité de temps qu'il faudrait pour montrer tous les nombres premiers à dix mille billions (10 élevé à la puissance seizième), d'autant plus que la calcul devient plus lent avec la gamme croissante. END_EDIT_ADD
Bien que la réponse par @SLaks fonctionne à l'aide de Linq, il est pas vraiment le Crible d'Eratosthène une doublure (genre de) car il est juste une version de non optimisé Section de première instance , en ce qu'elle non optimisé ne supprime pas les nombres premiers impairs, ne commence pas à la place du premier de base trouvée, et ne se limite pas pour l'abattage base de nombres premiers plus grande que la racine carrée du nombre supérieur à tamis. Il est également assez lent en raison des multiples opérations d'énumération imbriquées.
Il est en fait un abus de la méthode globale LINQ et ne pas utiliser de manière efficace la première des deux Linq Range de produit. Il peut devenir une Section de première instance optimisée avec moins de frais généraux d'énumération 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 se déroule plusieurs fois plus vite que les SLaks répondre. Cependant, il est encore lent et une mémoire à forte intensité due à la génération de la liste et les multiples énumérations ainsi que la fracture multiple (implicite) par le modulo opérations.
La vraie Sieve de mise en œuvre Eratosthène suivante dure environ 30 fois plus rapide et prend beaucoup moins de mémoire car il utilise seulement une représentation d'un bit par numéro tamisé et limite son énumération à la sortie de séquence de iterator finale, ainsi avoir les Optimisations de ne traiter que composites impairs, et l'abattage seulement des carrés des nombres premiers de la base de nombres premiers de base jusqu'à 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 à dix millions en gamme environ 77 millisecondes sur un processeur Intel i7-2700K (3,5 GHz).
Chacune des deux méthodes statiques peuvent être appelés et testé avec les déclarations et en utilisant la méthode principale statique 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 indique le nombre de nombres premiers dans la séquence jusqu'à la limite, la last premier trouvé, et le temps consacré à l'énumération jusque-là.
Edit_add: Toutefois, afin de produire une énumération du nombre de nombres premiers moins de dix mille billions (dix à la seizième puissance) que la question demande une approche paginée segmentée en utilisant multi-core le traitement est nécessaire, mais même avec C ++ et le PrimeSieve très optimisé , cela nécessiterait un peu plus de 400 heures pour produire seulement le nombre de nombres premiers trouvés, et des dizaines de fois long d'énumérer tous si plus d'un an pour faire ce que la question demande. Pour le faire en utilisant l'algorithme Section de première instance un optimisé tenté, il faudra des super éons et un très très longtemps, même en utilisant un algorithme Section de première instance optimisé comme quelque chose comme dix à deux ans de puissance millionième (qui est de deux millions de zéros années !! !).
Il n'y a pas beaucoup étonnant que sa machine de bureau assis juste et quand il a calé essayé !!!! S'il avait essayé une gamme plus petite, comme un million, il aurait encore trouvé qu'il faut dans la gamme de secondes mis en œuvre.
Les solutions que je poste ici ne sera pas coupé soit comme même le dernier Sieve d'Eratosthène un, il faudra environ 640 téraoctets de mémoire pour cette gamme.
C'est pourquoi seule une page approche segmentée comme celle de PrimeSieve peut gérer ce genre de problème pour la plage comme spécifié du tout, et même cela nécessite un temps très long, comme au cours des semaines à des années à moins d'avoir accès à un super-ordinateur avec des centaines de milliers de cœurs. END_EDIT_ADD
Smells comme plus de devoirs. Mon très très vieille calculatrice graphique avait un programme est le premier comme celui-ci. Technnically la boucle de contrôle de devision interne a seulement besoin de fonctionner à i ^ (1/2). Avez-vous besoin de trouver « tous les » nombres premiers entre 0 et L? L'autre problème majeur est que vos variables de boucle sont « int », tandis que vos données d'entrée est « long », ce sera à l'origine d'un débordement de faire vos boucles ne parviennent pas à exécuter même une fois. Fixer les variables de boucle.
Un code de ligne 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()));
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
La semence de l'agrégat doit être comprise entre 1 et num puisque cette liste contiendra la liste finale des nombres premiers. Le Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) est le nombre de fois où la graine est purgé.
ExchangeCore Forums ont une bonne application console liste qui ressemble à écrire des nombres premiers trouvés dans un fichier, il semble que vous pouvez également utiliser le même fichier en tant que point de départ afin que vous ne devez pas redémarrer la recherche des nombres premiers de 2 et ils fournissent un téléchargement de ce fichier avec tous trouvé les nombres premiers jusqu'à 100 millions alors que ce serait un bon point de départ.
L'algorithme sur la page aussi prend des raccourcis couple (nombres impairs et ne vérifie jusqu'à la racine carrée) ce qui le rend extrêmement efficace et il vous permettra de calculer le nombre de longs.
c'est donc essentiellement seulement deux fautes de frappe , l'un, le plus malheureux, for (int j = 2; j <= num; j++) qui est la raison de l'essai improductif de 1%2,1%3 ... 1%(10^15-1) qui se poursuit pendant très longtemps si l'OP n'a pas obtenu < em> "toute sortie" . Il aurait dû être j < i; à la place L'autre, un mineur en comparaison, est que i devrait commencer à partir de 2, pas de 0:.
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
Certes, on ne peut raisonnablement attendre d'un impression sur la console de 28 billions de nombres premiers ou alors à compléter en tout-délai raisonnable. Ainsi, l'intention initiale du problème était évidemment d'imprimer un flux régulier de nombres premiers, indéfiniment . D'où toutes les solutions proposant une utilisation simple de tamis d'Eratosthène sont totalement sans fondement ici, parce que simples crible d'Eratosthène est délimité - une limite doit être fixée à l'avance.
Ce qui pourrait travailler est la division d'essai optimisé ici qui permettrait de sauver les nombres premiers comme il les trouve, et un test contre les nombres premiers, et pas seulement tous les chiffres du candidat.
Deuxième autre, avec une meilleure complexité (c.-à-beaucoup plus rapide) est d'utiliser un tamis segmenté de Eratosthène . Ce qui est progressive et sans bornes.
Ces deux régimes utiliseraient production double mise en scène de nombres premiers : on pourrait produire et enregistrer les nombres premiers, pour être utilisé par l'autre étape dans les essais (ou tamiser), bien au-dessus de la limite de la première étape (ci-après son carré bien sûr - étendre automatiquement la première étape, en tant que deuxième étape serait aller plus loin et plus haut).
Pour être tout à fait franc, quelques-unes des solutions proposées sont vraiment lent, et sont donc mauvaises suggestions. Pour tester un numéro unique d'être le premier opérateur vous besoin de division / modulo, mais pour le calcul d'une plage que vous ne devez pas.
Fondamentalement, vous exclurent des chiffres qui sont des multiples de nombres premiers trouvés plus tôt, comme le sont-(par définition) ne se sont pas des nombres premiers.
Je ne vais pas donner la pleine mise en œuvre, ce serait facile, c'est l'approche dans le code pseudo. (Sur ma machine, la mise en œuvre effective calcule tous les nombres premiers dans un Sytem.Int32 (2 bilion) dans les 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 binaires. Mais il les moyens, et des moyens plus rapides. Vous pouvez également sûr le résultat du résultat sur le disque, si vous en avez besoin pour une utilisation ultérieure. Le résultat de 17 * 10 ^ 9 chiffres peut être safed avec 1 Go, et le calcul de ce jeu de résultats prend environ 2 minutes max.
Je sais que c'est calme vieille question, mais après avoir lu ici: Sieve de Eratosthène Wiki
Ceci est la façon dont je l'ai écrit de comprendre l'algorithme:
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
Dans la première boucle, nous remplissons le tableau de booléens avec vrai.
Deuxième boucle commencera à partir de 2 depuis 1 n'est pas un nombre premier et vérifiera si le nombre premier est toujours pas changé et puis attribuez-lui de faux à l'index j.
dernière boucle, nous affichons juste quand il est premier.
Très semblable - d'un exercice pour mettre en œuvre des Eratosthène en Sieve 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;
}
}
Prime Helper calcul très rapide
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
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();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
U peut utiliser le concept de nombre premier normale doit seulement deux facteurs (l'un et lui-même). Donc, faire comme ça, 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();
}
}
}
Cette solution affiche tous les nombres premiers entre 0 et 100.
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
Ceci est le meilleur moyen de 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");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
Il existe des moyens très optimales pour mettre en œuvre l'algorithme. Mais si vous ne savez pas beaucoup sur les mathématiques et vous suivez simplement la définition de prime que l'exigence: un nombre qui est divisible par 1 et par lui-même (et rien d'autre), voici un simple à comprendre le 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;
}
Étant donné que chaque nombre est divisible par 1 et par lui-même, nous commençons à vérifier à partir de 2 partir jusqu'à ce que le numéro immédiatement avant lui-même. C'est le raisonnement de base.
Vous pouvez aussi faire ceci:
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
