Como você gerar um usuário quantidade definida de números primos?

Question

Eu estou tentando gerar números primos com base na entrada do usuário. Isto é o que eu tenho até agora, mas eu simplesmente não consigo descobrir isso:

Console.Write("Please enter the number of prime numbers you would like to see:");
int numberOfPrimes = Convert.ToInt32(Console.ReadLine());

for (int x = 0; x < numberOfPrimes; x++)
{
    for (int a = 2; a <= x ; ++a)
    {
        bool prime = true;
        for (int b = 2; b < a; ++b)
        {
            if (a % b == 0)
            {
                prime = false;
            }//end if
        }//end double nested for
        if (prime == true)
        {
            Console.WriteLine(a);
        }//end if
    }//end nested for
}//end for

Answer 1

Você deve ser capaz de ver por que seus resultados estão errados bastante facilidade se você olhar para as suas estruturas de loop. Passo através deles com a mão (não vai demorar muito tempo).

A razão que você está recebendo os resultados atuais é que não cada iteração do loop externo (x < numberOfPrimes) produz um resultado -. Ele vai pular algumas iterações devido à forma como o loop interno está estruturado

O que você realmente precisa fazer é reestruturar os laços internos. Seu laço mais interno funciona bem, e deve detectar quaisquer números primos. Sua segunda volta, no entanto, só deve testar números que ainda não foram testadas. Além disso, ele deve parar de looping uma vez que você encontrar um número primo.

Answer 2

Você deve estruturar seu código melhor, é realmente confuso a maneira de fazê-lo agora. Tenha um IsPrime(int x) método que retorna true se x é primo e falso caso contrário.

Então, para gerar números primos numberOfPrimes, você pode fazer algo como isto:

for ( int primeCount = 0, currentPrime = 2; primeCount < numberOfPrimes; ++currentPrime )
  if ( IsPrime(currentPrime) )
  {
    // do whatever you want with currentPrime, like print it
    ++primeCount;
  }

Ou use o Crivo de Eratóstenes , que é um método muito mais rápido.

Para descobrir se um número x é primo ou não, tente todos os seus fatores entre 2 e Sqrt(x). Por que só Sqrt(x)? Porque se a*b = x, então x / b = a e x / a = b, Então você iria verificar tudo duas vezes, e também verificar as coisas que você não deve se você subiu para x / 2 ou mesmo x.

Assim, algo parecido com isso, se você quiser usar a função IsPrime(x):

// i <= Sqrt(x) <=> i * i <= x
for ( int i = 2; i * i <= x; ++i )
  if ( x % i == 0 )
    return false;

return true;

Mas eu sugiro que você use a peneira de Eratóstenes, como é muito mais rápido. Você pode também coisas otimizar para que você não verificar até mesmo números, uma vez que um número ainda nunca é privilegiada, exceto para 2 (ambos na peneira e o método ingênuo). Mimo x = 2 como um caso extremo e, em seguida, começar a verificar qualquer outro número (3, 5, 7, 9, 11, etc.)

Answer 3

O que você está procurando é chamado de "Crivo de Eratóstenes". Como eu não estou a fazer lição de casa das pessoas, esta é a única pista que eu vou dar-lhe. O algoritmo é facilmente encontrado na internet.

Answer 4

O próximo número primo (x) - é o número que não pode ser dividido por todos primos s, que s <= sqrt (x). Então você pode usar a função como

public bool CheckAndAddPrime(int number,List<int> primes)
{
    var sqrt = Math.Sqrt(number);
    foreach(var prime in primes)
    {
        if(prime>sqrt) break;
        if(number % prime == 0) return false;    
    }

    primes.Add(number);
    return true;
}

E do que você pode obter números primos como

var primes = new List<int>();
Enumerable.Range(2,int.MaxValue).Where(x => x.CheckAndAddPrime(x,primes)).Take(YouCountOfPrimes);

Answer 5

var primes = Enumerable.Range(1, numberOfPrimes )
    .Where(x => x != 1 &&
      !Enumerable.Range2, (int)Math.Sqrt(x)).Any(y => x != y && x % y == 0));

copiado de codethinked.com

static void Main(string[] args)
{
    foreach (int no in get_first_k_primes(10))
    {
        Console.Write(" "+no.ToString() );
    }
}

public static List<int> get_first_k_primes(int k)
{
    var primes = new List<int>();

    primes.Add(2);

    int i  = 3;


    while(primes.Count < k)
    {
        if(is_prime(i))
            primes.Add(i);

        i += 2;
    }

    return primes;
}

public static bool is_prime(int n)
{
    if (n % 2 == 0 && n != 2) return false;

    int m = (int)Math.Ceiling(Math.Sqrt(n));

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

    return true;
}

Answer 6

1. Renomear suas variáveis.

Em primeiro lugar, se esta é a lição de casa você vai ter más notas (se o seu professor é vale o seu sal), porque você tem nomes de variáveis ??sem sentido (sim, mesmo numberOfPrimes está errado e deve ser nomeado requiredNumberOfPrimes. Quando vejo esta variável Estou pedindo me 'é este quantas ele quer, ou quantos ele encontrou?').

Em segundo lugar, ele vai ajudar você a entender onde você está indo errado. As variáveis ??devem ser logicamente nomeados de acordo com o que eles representam. Se você não pode explicar o que suas variáveis ??representam (por exemplo, a & b), então você provavelmente não pode explicar o que você está fazendo com eles.

2. Olhada em seus loops.

for (int x = 0; x < numberOfPrimes; x++)

A estrutura de um loop é (initialise; 'should I continue?'; 'each loop do this'). Portanto, em seu loop

• Você está continuando até x é igual ou grande que numberOfPrimes *.
• Cada vez que você vá através do laço que você está adicionando 1 a x.

Tem certeza que isso é o que você quer fazer? x aparece para representar o número de primos que você encontrou. Então por que não incrementá-lo quando você encontra um primo, em vez de quando você começa um loop?

for (int a = 2; a <= x ; ++a)
for (int b = 2; b < a; ++b)

Você está olhando para cada inteiro entre 2 e x, inclusive. E para cada um desses números inteiros a, você está olhando para cada número inteiro entre a e 2 inclusive. O que você vai fazer com esses números inteiros?

Cada vez que você percorrer o loop de nível superior (o loop x), você vai começar o seu ciclo a a partir do zero, e cada vez que você percorra o seu ciclo a você vai começar o seu ciclo b a partir do zero.

Então, se x é 10, você corre através de uma só vez (a = 2), então você corre através de um novo (a = 2, a = 3), então você corre através de um novo (a = 2, a = 3 , a = 4), em seguida, ...

3. Recolher os seus resultados em vez de gravá-los no Console.

var primes = new List<int>();

É tão fácil. Quando você encontrar um número primo, primes.Add(a);. Então você sabe quantos primos você encontrou (primes.Count), você pode usar a lista de números primos para determinar de forma eficiente o primeiro seguinte, e você pode usar a lista mais tarde, se necessário.

Answer 7

Depois de fazer ithe se laços resolvido, você só tem que verificar se há b