Programa para encontrar números primos
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu quero encontrar o número primo entre 0 e uma variável muito tempo, mas eu não sou capaz de conseguir qualquer saída.
O programa é
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();
}
}
}
qualquer um pode me ajudar e encontrar o que é o possível erro no programa?
Solução
Você pode fazer isso mais rápido usando um quase ideal peneira divisão julgamento em uma (longa) linha 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;
}
);
A fórmula de aproximação para o número de primos usados ??aqui é π(x) < 1.26 x / ln(x) . Nós só precisamos de teste por primes não maior do que x = sqrt(num) .
Note que a peneira de Eratóstenes tem complexidade de tempo muito melhor do que correr divisão julgamento (deve ser executado muito mais rápido para maior num valores, quando devidamente implementado).
Outras dicas
Tente isto:
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;
}
}
Você só precisa verificar divisores ímpares até a raiz quadrada do número. Em outras palavras suas necessidades laço interno para começar:
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
Você também pode sair da função assim que encontrar o número não é primo, você não precisa verificar mais nenhuma divisores (Vejo você já está fazendo isso!).
Isso só vai funcionar se num é maior do que dois.
No Sqrt
Você pode evitar o Sqrt por completo, mantendo uma soma parcial. Por exemplo:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
Isto é porque a soma dos números 1 + (3 + 5) + (7 + 9) vai dar-lhe uma sequência de quadrados ímpares (1,9,25 etc). E, portanto, j representa a raiz quadrada de square_sum. Enquanto square_sum é inferior a i então j é menor do que a raiz quadrada.
As pessoas têm mencionou um par dos blocos de construção em direção a fazer isso de forma eficiente, mas ninguém é realmente colocar os pedaços juntos. A peneira de Eratóstenes é um bom começo, mas com ele você vai ficar sem memória < em> longo antes de atingir o limite que você definiu. Isso não significa que é inútil embora - quando você está fazendo o seu ciclo, o que você realmente se preocupam são divisores primos. Como tal, você pode começar usando a peneira para criar uma base de divisores primos, então use os do loop para números de teste pela primazia.
Quando você escreve o loop, no entanto, você realmente não querem nos sqrt (i) na condição de loop como um par de respostas sugeriram. Você e eu sabemos que o sqrt é uma função "pura" que dá sempre a mesma resposta se dado o mesmo parâmetro de entrada. Infelizmente, o compilador não sabe que, por isso, se usar algo como '<= Math.sqrt (x)' na condição de loop, ele vai voltar a calcular a raiz quadrada do número cada iteração do loop.
Você pode evitar que um par de maneiras diferentes. Você pode pré-computar o sqrt antes do loop, e usar o valor pré-calculado na condição de loop, ou você pode trabalhar em outra direção, e mudança i<Math.sqrt(x) para i*i<x. Pessoalmente, eu pré-calcular a raiz quadrada embora - Eu acho que é mais claro e, provavelmente, um pouco mais rápido - mas isso depende do número de iterações do loop (os meios i*i ele ainda está fazendo uma multiplicação no circuito). Com apenas algumas iterações, i*i será tipicamente mais rápido. Com iterações suficientes, a perda de i*i cada iteração supera o tempo para a execução de sqrt uma vez fora do loop.
Isso é provavelmente adequado para o tamanho de números que você está lidando com - um limite de 15 dígitos significa a raiz quadrada é de 7 ou 8 dígitos, que se encaixa em uma quantidade bastante razoável de memória. Por outro lado, se você quer lidar com números nesta faixa muito, você pode querer olhar para alguns dos algoritmos de verificação de primos mais sofisticados, tais como algoritmos do de Pollard ou Brent . Estes são mais complexas (para dizer o mínimo), mas um muito mais rápido para grandes números.
Existem outros algoritmos para números ainda maiores ( quadrática peneira , campo de número geral peneira ), mas não vamos entrar na deles para o momento - eles são muito mais complexo , e realmente útil apenas para lidar com números muito grandes (o GNFS começa a ser útil na faixa 100+ dígito).
Primeiro passo: escrever um método de extensão para saber se uma entrada é primo
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 passo: escrever o método que irá imprimir todos os números primos que estão entre 0 e a entrada do número
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
Pode ser apenas minha opinião, mas há um outro erro grave no seu programa (deixando de lado a determinada pergunta 'número primo', que foi completamente respondida).
Como o resto dos respondentes, estou assumindo que esta é a lição de casa, o que indica que você quer se tornar um desenvolvedor (presumivelmente).
Você precisa aprender a compartimentalizar seu código. Não é algo que você sempre precisa fazer um projeto, mas é bom saber como fazê-lo.
Seu método prime_num (long num) poderia ficar um nome melhor, mais descritivo. E se é suposto encontrar todos os números primos menos de um determinado número, ele deve devolvê-los como uma lista. Isto torna mais fácil para separar seu monitor e sua funcionalidade.
Se ele simplesmente retornou um IList contendo números primos você poderia então mostrar-los em sua função principal (talvez chamando outra função fora para muito imprimi-los) ou utilizá-los em outros cálculos para baixo da linha.
Assim, a minha melhor recomendação para você é fazer algo parecido com isto:
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() );
}
}
Mesmo se você acabar em algum lugar onde não é necessário speration assim trabalhando, é bom saber como fazê-lo.
EDIT_ADD: Se Will Ness é correto que o propósito da pergunta é apenas para a saída de um fluxo contínuo de primos durante o tempo que o programa é executado (pressionando Pause / Break para fazer uma pausa e qualquer tecla para iniciar novamente) sem qualquer esperança séria de cada chegar a esse limite superior, em seguida, o código deve ser escrito com nenhum argumento limite superior e um cheque leque de "true" para o primeiro 'i' para loop. Por outro lado, se a questão queria realmente imprimir os números primos até um limite, então o seguinte código irá fazer o trabalho muito mais eficiente usando tentativa Divisão apenas para números ímpares, com a vantagem que ele não usa memória de todos (que também pode ser convertido a um ciclo contínuo de acordo com o acima):
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);
}
}
Primeiro, o código questão não produz saída por causa disso suas variáveis ??de laço são inteiros e o limite testado é um grande inteiro longo, o que significa que é impossível para o loop para atingir o limite de produzir um loop interno EDITADO: em que a variável 'j' um circuito de retorno em torno de números negativos; quando a variável 'j' volta em torno de -1, o número testado falhar o teste de injeção, porque todos os números são divisíveis por -1
Isso leva uma hora ou mais para exibir os números primos até um bilhão, para que se possa imaginar a quantidade de tempo que seria necessário para mostrar todos os números primos de dez mil trilhões (10 elevado à potência XVI), especialmente porque a cálculo fica mais lento com o aumento da gama. END_EDIT_ADD
Embora o um forro (tipo de) resposta por @SLaks usando Linq funciona, não é realmente o Crivo de Eratóstenes, pois é apenas uma versão unoptimised de teste Divisão , unoptimised na medida em que não elimina primos ímpares, não começa na praça do prime de base encontrados, e não parada abate para primos base maior do que a raiz quadrada do número superior a peneira. Ele também é bastante lento devido às múltiplas operações de enumeração aninhada.
Na verdade, é um abuso do método Linq agregada e não usar eficazmente o primeiro dos dois Linq Faixa de gerado. Pode tornar-se uma secção de julgamento otimizado com menos de enumeração sobrecarga da seguinte forma:
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 funciona muitas vezes mais rápido do que a resposta SLaks. No entanto, ainda é lento e intensivo de memória devido à geração de lista e os vários enumerações, bem como a divisão múltipla (implícito no modulo) operações.
Os seguintes verdadeiros Crivo de Eratóstenes de implementação é executado cerca de 30 vezes mais rápido e leva muito menos memória que ele usa apenas uma representação um pouco por número peneirada e limita a sua enumeração para a saída sequência iterador final, bem com as otimizações de única tratamento compósitos ímpares, e apenas o abate dos quadrados dos números primos de base para primos de base até a raiz quadrada do número máximo, como se segue:
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; } }
O código acima calcula todos os números primos para dez milhões de gama em cerca de 77 milissegundos em um processador Intel i7-2700K (3,5 GHz).
Qualquer um dos dois métodos estáticos podem ser chamados e testados com as demonstrações usando e com o método principal estático da seguinte forma:
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 irá mostrar o número de números primos na sequência até ao limite, o last constatada privilegiada, e o tempo gasto em enumerar tão longe.
EDIT_ADD: No entanto, a fim de produzir uma enumeração do número de primos menos de dez mil trilhões (dez ao poder XVI) como a pergunta é, uma abordagem paginado segmentado usando multi-core processamento é necessário, mas mesmo com C ++ eo muito altamente otimizado PrimeSieve , isso exigiria algo mais de 400 horas para apenas produzir o número de primos encontrados, e dezenas de vezes tanto tempo para enumerar todos eles para mais de um ano para fazer o que a questão pede. Para fazê-lo usando o teste Divisão algoritmo-un otimizado tentativa, ele terá de super eras e uma muito, muito tempo mesmo usando um algoritmo de teste Divisão otimizado como em algo como dez a dois anos de poder milionésimo (que é de dois milhões de zeros anos !! !).
Não é muito de admirar que a sua máquina desktop apenas sentado e parado quando ele tentou fazê-lo !!!! Se ele tivesse tentado uma escala menor, como um milhão, ele ainda teria encontrado que leva na faixa de segundos, como implementado.
As soluções que eu postar aqui não vai cortá-lo tanto como até mesmo o último Crivo de Eratóstenes um vai exigir cerca de 640 terabytes de memória para esse intervalo.
É por isso que somente uma página segmentada abordagem como a do PrimeSieve pode lidar com esse tipo de problema para o intervalo como especificado em tudo, e mesmo que requer um tempo muito longo, como em semanas a anos menos que se tenha acesso a um super-computador com centenas de milhares de núcleos. END_EDIT_ADD
Cheira a mais lição de casa. Minha calculadora gráfica muito, muito velho tinha um é primo programa como este. Technnically o devision loop de verificação interna só precisa correr para i ^ (1/2). Você precisa encontrar "todos" os números primos entre 0 e L? O outro grande problema é que as variáveis ??de laço são "int", enquanto os dados de entrada é "longo", este será causar um estouro fazendo seus loops deixar de executar uma vez sequer. Corrigir as variáveis ??de laço.
Um código de linha em 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()));
O Crivo de resposta Eratóstenes acima não é totalmente correcta. Como escrito que vai encontrar todos os números primos entre 1 e 1000000. Para encontrar todos os números primos entre 1 e utilização 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;
}
);
}
A semente do agregado deve ser entre 1 e num vez que esta lista conterá a lista final dos números primos. O Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) é o número de vezes que a semente é purgado.
ExchangeCore Fóruns ter um bom aplicação de consola listados que olha para gravação encontrada primos para um arquivo, parece que você também pode usar esse mesmo arquivo como um ponto de partida para que você não tem que reiniciar encontrar números primos entre 2 e fornecem um download do arquivo com todos encontrados apronta-se para 100 milhões por isso seria um bom começo.
O algoritmo na página também leva um par de atalhos (números ímpares e apenas verifica até a raiz quadrada), o que faz com que seja extremamente eficiente e que lhe permitirá calcular números longos.
de modo que este é, basicamente, apenas dois erros , um, o mais lamentável, for (int j = 2; j <= num; j++) que é a razão para o teste improdutiva de 1%2,1%3 ... 1%(10^15-1) que se prolonga por muito tempo para que o OP não conseguiu < em> "qualquer saída" . Ele deveria ter sido j < i; vez O outro, menor um em comparação, é que i deve começar a partir de 2, não a partir de 0:.
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
Com certeza ele não pode ser razoavelmente esperado de um consola print-out de 28 trilhões de números primos ou mais para ser concluído em qualquer período de tempo razoável. Assim, a intenção original do problema era, obviamente, para imprimir um fluxo constante de números primos, indefinidamente . Daí todos os propondo soluções simples uso de peneira de Eratóstenes são totalmente sem mérito aqui, porque simples peneira de Eratóstenes é limitado - um limite deve ser definido com antecedência.
O que poderia trabalhar aqui é a divisão otimizada julgamento que iria salvar os primos como ele encontra-los, e teste contra os primos, e não apenas todos os números abaixo do candidato.
segunda alternativa, com muito melhor complexidade (ou seja, muito mais rápido) é a utilização de um
Ambos estes esquemas se usar
Para ser franco, algumas das soluções sugeridas são muito lento e, portanto, são maus sugestões. Para testar um único número para ser primo você precisa de algum operador de divisão / modulo, mas para calcular um intervalo que você não tem que.
Basicamente, você só excluir números que são múltiplos de números primos encontrados anteriormente, como o são (por definição) não apronta-se.
Eu não vou dar a plena implementação, como isso seria fácil, esta é a abordagem em pseudo-código. (Na minha máquina, a implementação real calcula todos os números primos em uma bilion Sytem.Int32 (2) 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.
}
}
A solução requer uma boa compreensão de operações bit a bit. Mas maneiras e maneiras mais rápidas. Você pode também segura o resultado do resultado no disco, se você precisar deles para uso posterior. O resultado de 17 * 10 ^ 9 números podem ser safed com 1 GB, e o cálculo do referido conjunto de resultados leva cerca de 2 minutos no máximo.
Eu sei que isso é calma questão de idade, mas depois de ler aqui: Crivo de Eratóstenes Wiki
Esta é a maneira que eu escrevi de compreender o 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 + " ");
}
No primeiro loop que preencher a matriz de booleanos com verdade.
Segundo loop vai começar a partir de 2 desde 1 não é um número primo e irá verificar se número primo ainda não é alterado e, em seguida, falso atribuir ao índice de j.
último laço que apenas imprimir quando ele é primo.
Muito semelhante - a partir de um exercício para implementar Crivo de Eratóstenes em 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;
}
}
Primeiro-Helper cálculo muito 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 pode usar o conceito normal de número primo deve apenas dois fatores (um e em si). Então faça assim, caminho mais 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 solução exibe todos os números primos entre 0 e 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 é a maneira mais rápida para calcular números primos em 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);}
}
}
}
Existem algumas maneiras muito melhores para implementar o algoritmo. Mas se você não sabe muito sobre matemática e você simplesmente seguir a definição de primordial como a exigência: um número que só é divisível por 1 e por si mesmo (e nada mais), aqui está um simples de entender o código para 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;
}
Uma vez que cada número é divisível por 1 e por si mesmo, começamos a verificação de 2 em diante até que o número imediatamente antes si. Esse é o raciocínio básico.
Você pode fazer também isto:
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;
}
}
