Progtwig para encontrar números primos

Quiero encontrar el número primo entre 0 y una variable larga, pero no puedo obtener ningún resultado.

El progtwig es

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(); } } } 

¿Alguien puede ayudarme y encontrar cuál es el posible error en el progtwig?

    Puede hacerlo más rápido usando un tamiz de división de prueba casi óptimo en una línea (larga) como esta:

     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 fórmula de aproximación para el número de primos usados ​​aquí es π(x) < 1.26 x / ln(x) . Solo necesitamos probar por números primos no mayores que x = sqrt(num) .

    Tenga en cuenta que el tamiz de Eratóstenes tiene una complejidad de tiempo de ejecución mucho mejor que la división de prueba (debe ejecutarse mucho más rápido para valores num más grandes, cuando se implementa correctamente).

    Prueba esto:

     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; } } 

    La gente ha mencionado algunos de los componentes básicos para hacer esto de manera eficiente, pero nadie realmente ha juntado las piezas. El colador de Eratóstenes es un buen comienzo, pero con él te quedarás sin memoria mucho antes de que llegues al límite que has establecido. Sin embargo, eso no significa que sea inútil: cuando haces tu ciclo, lo que realmente te importa son los divisores principales. Como tal, puede comenzar utilizando el tamiz para crear una base de divisores primos, luego use aquellos en el ciclo para probar la primacía de los números.

    Sin embargo, cuando se escribe el ciclo, realmente NO se quiere que sqrt (i) esté en la condición de ciclo, como lo sugirieron algunas respuestas. Tú y yo sabemos que el sqrt es una función “pura” que siempre da la misma respuesta si se le da el mismo parámetro de entrada. Desafortunadamente, el comstackdor NO lo sabe, así que si usa algo como ‘< = Math.sqrt (x)' en la condición de bucle, volverá a calcular el sqrt del número en cada iteración del ciclo.

    Puedes evitar eso de dos maneras diferentes. Puede precomputar el sqrt antes del bucle y usar el valor precalculado en la condición de bucle, o puede trabajar en la otra dirección y cambiar i

    por i*i . Personalmente, calcularía previamente la raíz cuadrada, creo que es más clara y probablemente un poco más rápida, pero eso depende del número de iteraciones del ciclo (el i*i significa que todavía está haciendo una multiplicación en el ciclo ) Con solo unas pocas iteraciones, i*i normalmente seré más rápido. Con suficientes iteraciones, la pérdida de i*i cada iteración supera el tiempo de ejecución de sqrt una vez fuera del ciclo.

    Eso es probablemente adecuado para el tamaño de los números con los que se trata: un límite de 15 dígitos significa que la raíz cuadrada es de 7 u 8 dígitos, lo que se ajusta a una cantidad bastante razonable de memoria. Por otro lado, si desea tratar mucho los números en este rango, es posible que desee ver algunos de los algoritmos de comprobación primaria más sofisticados, como los algoritmos de Pollard o Brent . Estos son más complejos (por decirlo suavemente) pero mucho más rápido para grandes números.

    Existen otros algoritmos para números incluso mayores ( tamiz cuadrático , tamiz de campo numérico general ) pero no los abordaremos por el momento; son mucho más complejos y realmente útiles solo para tratar con números realmente grandes (el GNFS comienza a ser útil en el rango de más de 100 dígitos).

    Solo necesita marcar divisores impares hasta la raíz cuadrada del número. En otras palabras, tu ciclo interno debe comenzar:

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

    También puede salir de la función tan pronto como descubra que el número no es primo, no necesita verificar más divisores (¡veo que ya está haciendo eso!).

    Esto solo funcionará si num es más grande que dos.

    No Sqrt

    Puede evitar el Sqrt por completo manteniendo una sum stream. Por ejemplo:

     int square_sum=1; for (int j=3; square_sum 

    Esto se debe a que la sum de los números 1+ (3 + 5) + (7 + 9) le dará una secuencia de cuadrados impares (1,9,25, etc.). Y, por lo tanto, j representa la raíz cuadrada de square_sum . Siempre que square_sum sea ​​menor que i , j es menor que la raíz cuadrada.

    Primer paso: escriba un método de extensión para averiguar si una entrada es primordial

     public static bool isPrime(this int number ) { for (int i = 2; i < number; i++) { if (number % i == 0) { return false; } } return true; } 

    2 pasos: escriba el método que imprimirá todos los números primos que estén entre 0 y el número ingresado

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

    Puede que sea solo mi opinión, pero hay otro error grave en su progtwig (dejando de lado la pregunta sobre el “número primo”, que ha sido completamente respondida).

    Al igual que el rest de los que respondieron, supongo que se trata de tarea, lo que indica que desea convertirse en un desarrollador (presumiblemente).

    Debes aprender a dividir tu código en compartimentos. No es algo que siempre necesitará hacer en un proyecto, pero es bueno saber cómo hacerlo.

    Su método prime_num (long num) podría soportar un nombre mejor y más descriptivo. Y si se supone que debe encontrar todos los números primos menores que un número dado, debería devolverlos como una lista. Esto facilita la separación de su pantalla y su funcionalidad.

    Si simplemente devolviera un IList que contiene números primos, podría mostrarlos en su función principal (tal vez llamando a otra función externa para imprimirlos bastante) o usarlos en cálculos posteriores en la línea.

    Entonces mi mejor recomendación es hacer algo como esto:

     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 primes = FindSmallerPrimes(number); DisplayPrimes(primes); } public IList FindSmallerPrimes(long largestNumber) { List returnList = new List(); //Find the primes, using a method as described by another answer, add them to returnList return returnList; } public void DisplayPrimes(IList primes) { foreach(long l in primes) { Console.WriteLine ( "Prime:" + l.ToString() ); } } 

    Incluso si termina trabajando en un lugar donde no se necesita una sesión como esta, es bueno saber cómo hacerlo.

    EDIT_ADD: Si Will Ness está en lo correcto, el propósito de la pregunta es simplemente emitir un flujo continuo de primos mientras se ejecuta el progtwig (presionando Pausa / Pausa para pausar y cualquier tecla para comenzar de nuevo) sin ninguna esperanza seria de llegar a ese límite superior, entonces el código debe escribirse sin un argumento de límite superior y una verificación de rango de “verdadero” para el primer bucle de ‘i’. Por otro lado, si la pregunta realmente quería imprimir los números primos hasta un límite, entonces el siguiente código hará el trabajo mucho más eficientemente usando la División de prueba solo para números impares, con la ventaja de que no usa memoria en absoluto (también podría convertirse en un bucle continuo según lo anterior):

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

    Primero, el código de pregunta no produce salida debido a que sus variables de bucle son enteros y el límite probado es un entero largo enorme, lo que significa que es imposible que el bucle llegue al límite produciendo un bucle interno EDITADO: por el cual la variable 'j' vuelve a los números negativos; cuando la variable 'j' vuelve a -1, el número probado falla la prueba principal porque todos los números son divisibles por -1 END_EDIT . Incluso si esto se corrigiera, el código de pregunta produce un resultado muy lento porque se divide haciendo divisiones de 64 bits de cantidades muy grandes de números compuestos (todos los números pares más los compuestos impares) por toda la gama de números hasta esa parte superior número de diez elevado a la decimosexta potencia para cada primo que posiblemente puede producir. El código anterior funciona porque limita el cálculo a solo los números impares y solo hace divisiones de módulo hasta la raíz cuadrada del número actual que se está probando .

    Esto demora alrededor de una hora en mostrar los números primos hasta mil millones, así que uno puede imaginar la cantidad de tiempo que tomaría mostrar todos los números primos a diez mil billones (10 elevado a la potencia dieciséis), especialmente a medida que el cálculo se vuelve más lento con un rango creciente END_EDIT_ADD

    Aunque la respuesta tipo liner (tipo de) de @SLaks con Linq funciona, no es realmente el Sieve of Eratosthenes, ya que es simplemente una versión no optimizada de Trial Division , sin pretender que no elimine los primos impares, no comience en el cuadrado de la base principal encontrada, y no detiene la eliminación de primos de base más grandes que la raíz cuadrada del número superior a tamizar. También es bastante lento debido a las múltiples operaciones de enumeración anidadas.

    En realidad, es un abuso del método de Agregado de Linq y no utiliza efectivamente el primero de los dos Rangos de Linq generados. Puede convertirse en una División de prueba optimizada con menos sobrecarga de enumeración de la siguiente manera:

     static IEnumerable 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; } 

    que se ejecuta muchas veces más rápido que la respuesta de SLaks. Sin embargo, todavía es lento y consume mucha memoria debido a la generación de listas y las enumeraciones múltiples, así como a las operaciones de división múltiple (implícitas en el módulo).

    La siguiente implementación de Sieve of Eratosthenes es aproximadamente 30 veces más rápida y requiere mucha menos memoria, ya que solo utiliza una representación de un bit por número filtrado y limita su enumeración a la salida final de secuencia de iterador, además de tener optimizaciones de solo tratar compuestos impares. y solo descarte de los cuadrados de los primos base para primos base hasta la raíz cuadrada del número máximo, de la siguiente manera:

     static IEnumerable 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; } } 

    El código anterior calcula todos los números primos a diez millones de rango en aproximadamente 77 milisegundos en un Intel i7-2700K (3.5 GHz).

    Cualquiera de los dos métodos estáticos se puede llamar y probar con las instrucciones de uso y con el método principal estático de la siguiente manera:

     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(); } 

    que mostrará el número de primos en la secuencia hasta el límite, el último primo encontrado y el tiempo empleado en enumerar ese extremo.

    EDIT_ADD: Sin embargo, para producir una enumeración del número de primos de menos de diez mil trillones (diez a la decimosexta potencia) como se pregunta, se requiere un enfoque paginado segmentado que use procesamiento multinúcleo, pero incluso con C ++ y el mismo altamente optimizado PrimeSieve , esto requeriría algo más de 400 horas para producir la cantidad de primos encontrados, y decenas de veces más tiempo para enumerarlos a todos durante más de un año para hacer lo que la pregunta plantea. Para hacerlo usando el algoritmo no optimizado de la División de Pruebas, llevará super eones y mucho tiempo incluso usando un algoritmo de la División de Prueba optimizado en algo así como diez o dos millones de años de poder (¡¡Eso es dos millones de años ceros !! !).

    ¡No es de extrañar que su computadora de escritorio se quedara parada cuando lo intentó! Si hubiera probado un rango más pequeño, como un millón, todavía habría encontrado que tarda en el rango de segundos según lo implementado.

    Las soluciones que publico aquí tampoco lo cortarán, ya que incluso el último Sieve of Eratosthenes requerirá alrededor de 640 Terabytes de memoria para ese rango.

    Es por eso que solo un enfoque segmentado por páginas como el de PrimeSieve puede manejar este tipo de problema para el rango especificado, e incluso eso requiere mucho tiempo, en semanas o años, a menos que uno tenga acceso a una súper computadora con cientos de miles de núcleos. END_EDIT_ADD

    Huele a más deberes Mi muy antigua calculadora gráfica tenía un progtwig principal como este. Técnicamente, el lazo de verificación de devision interno solo necesita ejecutarse en i ^ (1/2). ¿Necesita encontrar “todos” números primos entre 0 y L? El otro gran problema es que sus variables de bucle son “int” mientras que sus datos de entrada son “largos”, esto causará un desbordamiento que hace que sus bucles no se ejecuten ni siquiera una vez. Corrige las variables de bucle.

    La respuesta del Tamiz de Eratóstenes anterior no es del todo correcta. Tal como está escrito, encontrará todos los números primos entre 1 y 1000000. Para encontrar todos los números primos entre 1 y num use:

     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 semilla del Agregado debe ser de rango 1 a num, ya que esta lista contendrá la lista final de primos. El Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) es el número de veces que se purga la semilla.

    ExchangeCore Forums tiene una buena aplicación de consola listada que busca escribir primos encontrados en un archivo, parece que también puede usar ese mismo archivo como punto de partida para que no tenga que reiniciar la búsqueda de números primos desde 2 y proporcionan una descarga de ese archivo con todos los números primos encontrados hasta 100 millones por lo que sería un buen comienzo.

    El algoritmo en la página también toma un par de atajos (números impares y solo revisa hasta la raíz cuadrada) lo que lo hace extremadamente eficiente y le permitirá calcular números largos.

    Código de una línea 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())); 

    así que esto es básicamente solo dos errores tipográficos , uno, el más desafortunado, for (int j = 2; j < = num; j++) que es el motivo de la prueba improductiva del 1%2,1%3 ... 1%(10^15-1) que continúa durante mucho tiempo, por lo que el OP no obtuvo "ningún resultado" . Debería haber sido j < i; en lugar. El otro, menor en comparación, es que debería comenzar desde 2, no desde 0:

     for( i=2; i < = num; i++ ) { for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough .... 

    Seguramente no se puede esperar razonablemente que una impresión de consola de 28 trillones de primos se complete en un marco de tiempo razonable. Entonces, la intención original del problema era obviamente imprimir un flujo constante de primos, indefinidamente . Por lo tanto, todas las soluciones que proponen el uso simple del tamiz de Eratóstenes no tienen ningún mérito aquí, porque el simple tamiz de Eratóstenes está delimitado, se debe establecer un límite por adelantado.

    Lo que podría funcionar aquí es la división de prueba optimizada que salvaría los números primos tal como los encuentra, y probará los números primos, no solo todos los números debajo del candidato.

    La segunda alternativa, con una complejidad mucho mejor (es decir, mucho más rápida) es usar un tamiz segmentado de Eratóstenes . Que es incremental y sin límites.

    Ambos esquemas usarían producción de primos doble etapa: uno produciría y guardaría los primos, para ser usados ​​por la otra etapa en la prueba (o cribado), muy por encima del límite de la primera etapa (debajo de su cuadrado de curso - automáticamente extendiendo la primera etapa, ya que la segunda etapa iría más y más arriba).

    Para ser franco, algunas de las soluciones sugeridas son realmente lentas y, por lo tanto, son malas sugerencias. Para probar que un solo número sea primo necesita un operador de división / módulo, pero para calcular un rango no es necesario.

    Básicamente, usted excluye los números que son múltiplos de primos encontrados anteriormente, ya que son (por definición) no primos.

    No daré la implementación completa, ya que sería fácil, este es el enfoque en pseudo código. (En mi máquina, la implementación real calcula todos los números primos en un Sytem.Int32 (2 bilion) en 8 segundos.

     public IEnumerable 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 solución requiere una buena comprensión de las operaciones bit a bit. Pero es mucho más rápido. También puede proteger el resultado del resultado en disco, si los necesita para un uso posterior. El resultado de 17 * 10 ^ 9 números puede ser de seguridad con 1 GB, y el cálculo de ese conjunto de resultados toma aproximadamente 2 minutos como máximo.

    Muy similar: de un ejercicio para implementar Tamiz de Eratóstenes en C #:

     public class PrimeFinder { readonly List _primes = new List(); public PrimeFinder(long seed) { CalcPrimes(seed); } public List 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 cálculo muy rápido

     public static class PrimeHelper { public static IEnumerable FindPrimes(Int32 maxNumber) { return (new PrimesInt32(maxNumber)); } public static IEnumerable 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 { 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 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 puede usar el concepto de número primo normal solo debe tener dos factores (uno y sí mismo). Así que hazlo de esta manera fácil

     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(); } } } 

    Esta solución muestra todos los números primos entre 0 y 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 + " "); } } 

    Esta es la forma más rápida de calcular números primos 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"); } } 

    Sé que esta es una vieja y tranquila pregunta, pero después de leer aquí: Sieve of Eratosthenes Wiki

    Esta es la forma en que lo escribí al entender el algoritmo:

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

    In the first loop we fill the array of booleans with true.

    Second for loop will start from 2 since 1 is not a prime number and will check if prime number is still not changed and then assign false to the index of j.

    last loop we just printing when it is prime.