Programa para encontrar números primos
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Quiero encontrar el número primo entre 0 y un largo variable, pero no soy capaz de conseguir cualquier salida.
El programa 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();
}
}
}
Puede cualquiera que me ayude a cabo y encontrar cuál es el posible error en el programa?
Solución
Esto se puede hacer más rápido el uso de un casi óptima tamiz división de juicio en una línea (largo) de esta manera:
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 números primos se utiliza aquí es π(x) < 1.26 x / ln(x) . Tan sólo hay que probar por números primos no mayor que x = sqrt(num) .
Tenga en cuenta que el criba de Eratóstenes tiene mucho mejor tiempo de ejecución complejidad de la división de ensayo (se debe ejecutar mucho más rápido para los más grandes num los valores, si se aplica correctamente).
Otros consejos
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;
}
}
Sólo es necesario para comprobar divisores impares hasta la raíz cuadrada del número. En otras palabras, su bucle interno tiene que empezar:
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
También puede salir de la función tan pronto como se encuentre el número no es primo, que no es necesario para comprobar cualquier más divisores (Veo que ya está haciendo eso!).
Esto sólo funcionará si num es mayor que dos.
No sqrt
Puede evitar el sqrt por completo, manteniendo una suma continua. Por ejemplo:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
Esto se debe a la suma 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. Mientras square_sum es menor que i continuación j es menor que la raíz cuadrada.
La gente ha mencionado un par de los bloques de construcción hacia hacer esto de manera eficiente, pero nadie es realmente poner las piezas juntas. Los href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" es un buen comienzo, pero con él se puede quedar sin memoria < em> los antes de llegar al límite que ha establecido. Eso no quiere decir que es inútil sin embargo - cuando estás haciendo el bucle, lo que realmente se preocupan por son divisores primos. Como tal, puede comenzar utilizando el tamiz para crear una base de divisores primos, a continuación, utilizar aquellos en el bucle para probar los números por la primacía.
Cuando se escribe el bucle, sin embargo, que realmente no quiere sqrt (i) en la condición de bucle como un par de respuestas han sugerido. Usted y yo sabemos que la raíz cuadrada es una función "puro" que siempre da la misma respuesta si se les da el mismo parámetro de entrada. Por desgracia, el compilador no sabe que, por lo que si uso algo así como '<= Math.sqrt (x) en la condición de bucle, que va a volver a calcular la raíz cuadrada del número cada iteración del bucle.
Usted puede evitar que un par de maneras diferentes. Puede ya sea antes de calcular la raíz cuadrada antes del bucle, y utilizar el valor de pre-computados en la condición de bucle, o puede trabajar en la otra dirección, y cambiar a i<Math.sqrt(x) i*i<x. En lo personal, me pre-Calcular la raíz cuadrada aunque - Creo que es más clara y probablemente un poco más rápido - pero eso depende del número de iteraciones del bucle (la i*i significa que todavía está haciendo una multiplicación en el bucle). Con sólo unas pocas iteraciones, i*i normalmente será más rápido. Con suficientes iteraciones, la pérdida de i*i cada iteración es mayor que el tiempo para la ejecución de sqrt una vez fuera del bucle.
Eso es probablemente adecuado para el tamaño de los números que está tratando con - un límite de 15 dígitos significa la raíz cuadrada es de 7 u 8 dígitos, que encaja en una cantidad bastante razonable de memoria. Por otro lado, si usted quiere tratar con números en este rango mucho, es posible que desee ver en algunos de los más sofisticados algoritmos de comprobación de primera, como Brent algoritmos de Pollard o de . Estos son más complejos (por decirlo suavemente), sino un mucho más rápido para un gran número.
Hay otros algoritmos para un número aún más grandes ( cuadrática tamiz , criba general del cuerpo de números ) pero no vamos a entrar en ellos por el momento - son mucho más complejas , y realmente sólo es útil para tratar con números muy grandes (la GNFS empieza a ser útil en el rango de más de 100 dígitos).
Primer paso: escribir un método de extensión para averiguar si una entrada es primo
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 pasos: escribir el método que va a imprimir todos los números primos que están entre 0 y el número de entrada
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
Puede ser sólo mi opinión, pero no hay otro error grave en su programa (dejando a un lado el 'número primo' pregunta dada, que ha sido contestada a fondo).
Al igual que el resto de los respondedores, estoy suponiendo que esto es la tarea, lo que indica que desea convertirse en un desarrollador (presumiblemente).
Es necesario aprender a compartimentar su código. No es algo que siempre hay que hacer en un proyecto, pero es bueno saber cómo hacerlo.
Su método prime_num (larga num) podía soportar un nombre mejor, más descriptivo. Y si se supone que encontrar todos los números primos menores que un número dado, debe devolverlos en forma de lista. Esto hace que sea más fácil de separar de su pantalla y su funcionalidad.
Si simplemente se volvió un IList que contiene los números primos usted podría entonces los muestra en su función principal (tal vez llamar a otra función exterior para imprimir bastante ellos) o utilizarlos en cálculos posteriores en la línea.
Así que mi mejor recomendación para ti 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<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() );
}
}
Incluso si al final de trabajo en algún lugar donde no es necesaria speration como este, es bueno saber cómo hacerlo.
EDIT_ADD: Si Will Ness es correcto que el propósito de la cuestión es sólo para dar salida a un flujo continuo de números primos por el tiempo que se ejecuta el programa (pulsando Pausa / Pausa para hacer una pausa y cualquier tecla para iniciar de nuevo), sin esperanza seria de cada llegar a ese límite superior, entonces el código debe ser escrito sin ningún argumento límite superior y una prueba de alcance de la "verdadera" por primera 'i' para el lazo. Por otro lado, si la pregunta quería imprimir en realidad los números primos hasta un límite, entonces el siguiente código hará el trabajo mucho más eficiente el uso de sala de primera instancia sólo para los números impares, con la ventaja de que no utiliza la memoria en absoluto (que también podría ser convertido en un bucle continuo como por la 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);
}
}
En primer lugar, el código de pregunta no produce ninguna salida debido a que sus variables de bucle son números enteros y el límite probado es un enorme número entero de largo, lo que significa que es imposible para el bucle para alcanzar el límite producir un bucle interno Editado: mediante el cual el 'j' variable de bucle de vuelta alrededor para números negativos; cuando la variable 'j' llega de nuevo a -1, el número probado no pasa la prueba primo porque todos los números son divisibles por -1 END_EDIT . Incluso si esto se corrige, el código de pregunta produce una salida muy lenta, ya que se une haciendo divisiones de 64 bits de cantidades muy grandes de números compuestos (todos los números pares, además de los compuestos impares) por toda la gama de números hasta que la parte superior número de diez elevado a la potencia XVI para cada primo que posiblemente puede producir. El código anterior funciona, ya que limita el cómputo de sólo los números impares y sólo hace divisiones de módulo hasta la raíz cuadrada del número actual que está siendo probado .
Esto toma una hora o así para mostrar los números primos hasta un mil millones, por lo que uno se puede imaginar la cantidad de tiempo que se tardaría en mostrar todos los números primos a diez mil billones (10 elevado a la potencia XVI), sobre todo porque el cálculo se vuelve más lento con el aumento de rango. END_EDIT_ADD
A pesar de que el revestimiento (tipo de) la respuesta por @SLaks utilizando Linq funciona, en realidad no es la criba de Eratóstenes, ya que es sólo una versión de unoptimised Sección de Primera Instancia , unoptimised ya que no elimina primos impares, no se inicia en la plaza de la base de primer encontrado, y no se detiene para el sacrificio base de ceba más grande que la raíz cuadrada del número superior a tamiz. También es bastante lenta debido a las múltiples operaciones de enumeración anidada.
En realidad, es un abuso del método de LINQ agregada y no utiliza de manera efectiva el primero de los dos LINQ Rango del generada. Puede convertirse en una División Trial optimizado con menos sobrecarga enumeración como sigue:
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; }
que corre mucho más rápido que los SLaks responder. Sin embargo, todavía es lento y requiere mucha memoria debido a la generación de lista y las múltiples enumeraciones, así como la división múltiple (implicado por el módulo de operaciones).
La siguiente verdadera Criba de aplicación Eratóstenes funciona con cerca de 30 veces más rápido y tiene mucha menos memoria ya que sólo se utiliza una representación de un bit por número tamiza y se limita su enumeración a la final de salida de secuencia de iterador, así que tiene las optimizaciones de solamente tratar composites impares, y sólo el sacrificio de los cuadrados de los números primos de base para la base de primos hasta la raíz cuadrada del número máximo, como sigue:
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; } }
El código anterior calcula todos los números primos a diez millones de gama en unos 77 milisegundos en un procesador Intel i7-2700K (3,5 GHz).
Cualquiera de los dos métodos estáticos pueden ser llamados y probado con las instrucciones using y con el método principal estático como sigue:
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 números primos en la secuencia hasta el límite, el last primer encontró, y el tiempo gastado en la enumeración de tan lejos.
EDIT_ADD: Sin embargo, con el fin de producir una enumeración del número de números primos menos de diez mil billones (diez a la potencia decimosexta) como la cuestión pregunta, un enfoque paginado segmentado usando multi-núcleo se requiere un procesamiento pero incluso con C ++ y el muy altamente optimizado PrimeSieve , esto requeriría algo más de 400 horas a solo producen el número de primos que se encuentran, y decenas de veces que el largo enumerar todos ellos para más de un año para hacer lo que hace la pregunta. Para hacerlo utilizando el algoritmo de división de prueba sin optimizar intentó, tomará súper eones y un muy largo tiempo, incluso usando un algoritmo Sección de Primera Instancia optimizado como en algo así como diez a los dos años de poder millonésima (que es de dos millones de ceros años !! !).
No es de extrañar que tanto su máquina de escritorio sólo se sentó y se detuvo cuando trató él !!!! Si se hubiera tratado de un rango más pequeño, como un millón, todavía habría encontrado que se necesita en el rango de segundos tal como se aplica.
Las soluciones que publico aquí no se corte bien, ya que incluso la última criba de Eratóstenes uno requerirá alrededor de 640 terabytes de memoria para ese rango.
Esto es por qué sólo una página enfoque segmentado como el de PrimeSieve puede manejar este tipo de problema para el rango como se especifica en absoluto, e incluso eso requiere un tiempo muy largo, como en semanas o años si no se tiene acceso a una súper ordenador con cientos de miles de núcleos. END_EDIT_ADD
Huele más tarea. Mi calculadora gráfica muy, muy viejo tenía un programa es primordial como este. Technnically el bucle de comprobación devisiones interior sólo tiene que ejecutar para i ^ (1/2). ¿Necesita encontrar "todos" los números primos entre 0 y L? El otro gran problema es que sus variables de bucle son "int", mientras que los datos de entrada es "largo", esto va a ser la causa de un exceso de capacidad de hacer sus bucles no pueden ejecutar ni una sola vez. Fijar las variables de bucle.
Una línea de código 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()));
El criba de Eratóstenes respuesta anterior no es del todo correcto. Como está escrito que encontrará todos los números primos entre 1 y 1000000. Para encontrar todos los números primos entre 1 y el uso num:
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 rango de 1 a num ya que esta lista contendrá la lista final de los números primos. El Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) es el número de veces que se purgó la semilla.
ExchangeCore foros tienen un buen aplicación de consola en la lista que se parece a escribir los números primos que se encuentran en un archivo, parece que también se puede usar el mismo archivo como un punto de partida para que usted no tiene que reiniciar la búsqueda de números primos entre 2 y proporcionan una descarga de ese archivo con todas encontrado primos hasta 100 millones de dólares por lo que sería un buen comienzo.
El algoritmo de la página también tiene un par de atajos (números impares y sólo comprueba hasta la raíz cuadrada), que hace que sea muy eficiente y que le permitirá calcular números largos.
así que esto es básicamente sólo dos errores tipográficos , uno, el más desgraciado, for (int j = 2; j <= num; j++) que es la razón de la prueba improductivo de 1%2,1%3 ... 1%(10^15-1) la que se prolonga durante mucho tiempo por lo que el PO no consiguió < em> "ninguna salida" . lo que debería haber sido j < i; lugar La otra, de menor importancia en comparación, es que i debe partir de 2, no desde 0:.
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
Sin duda, no se puede esperar razonablemente de un consola de impresión de salida de 28 billones de números primos más o menos para completar en cualquier marco de tiempo razonable. Por lo tanto, la intención original del problema era, obviamente, para imprimir un flujo constante de los números primos, indefinidamente . Por lo tanto, todas las soluciones que proponen un uso simple de criba de Eratóstenes son totalmente sin mérito aquí, porque sencilla criba de Eratóstenes está delimitada - un límite debe establecerse de antemano.
Lo que podría trabajar aquí es la división optimizado juicio lo que ahorraría los números primos, ya que los encuentra, y la prueba en contra de los números primos, no sólo todos los números por debajo del candidato.
segunda alternativa, con mucho mejor la complejidad (es decir, mucho más rápido) es utilizar un tamiz segmentado de Eratóstenes . Que es gradual y sin límites.
Tanto estos esquemas usarían producción de doble etapas de números primos : uno podría producir y guardar los números primos, para ser utilizado por la otra etapa en la prueba (o tamizado), muy por encima del límite de la primera etapa (por debajo de su cuadrado de curso - que se extiende de forma automática la primera etapa, ya que la segunda etapa sería ir más lejos y más arriba).
Para ser franco, algunas de las soluciones propuestas son muy lento, y por lo tanto son malas sugerencias. Para el ensayo de un solo número para ser primer necesita algún operador de división / módulo, pero para calcular un rango que no tenga que hacerlo.
Básicamente que acaba de excluir números que son múltiplos de números primos que se facilitan, como son (por definición) no se prepara a sí mismos.
No daré la aplicación plena, ya que sería de 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 una Sytem.Int32 (2 bilion) dentro de 8 segundos.
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 solución requiere una buena comprensión de las operaciones bit a bit. Pero, formas y maneras más rápidas. También puede segura el resultado de los resultados en el disco, si los necesita para su uso posterior. El resultado de 17 * 10 ^ 9 números se puede safed con 1 GB, y el cálculo de dicho conjunto de resultados toma alrededor de 2 minutos como máximo.
Sé que esto es tranquila cuestión de edad, pero después de leer aquí: criba de Eratóstenes Wiki
Esta es la forma en que lo escribió de la comprensión del 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 + " ");
}
En el primer bucle que rellenar la matriz de booleanos con la verdadera.
En segundo bucle se iniciará desde 2 desde 1 no es un número primo y comprobará si todavía no se cambia número primo y luego asignar falsa al índice de j.
último bucle que acaba de imprimir cuando es primo.
Muy similar - a partir de un ejercicio para poner en práctica criba de Eratóstenes 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;
}
}
El primer ayudante de cálculo muy rápido
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 puede utilizar el número primo normales concepto debe sólo dos factores (uno y el mismo). También lo hacen así, forma 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 manera más rápida para 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");
}
}
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);}
}
}
}
Hay algunas maneras muy óptimas para implementar el algoritmo. Pero si usted no sabe mucho acerca de las cuentas y simplemente sigue la definición del primer como el requisito: un número que sólo es divisible por 1 y por sí mismo (y nada más), he aquí una sencilla de entender el código para los números positivos.
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;
}
Debido a que cada número es divisible por 1 y por sí mismo, comenzamos la comprobación de 2 en adelante hasta que el número inmediatamente antes de sí mismo. Ese es el razonamiento básico.
Se puede hacer también esto:
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;
}
}
