Desafio de fim de semana - Programa que detecte números primos
comentada em 05/01/2020 18:17

Certa vez fiz esse em Delphi e é brutal como ele usa processamento quando o número é grande. Chegava a gastar 20 minutos processando. Ele dividia o número que eu digitasse por todos até ele mesmo e falava se o número que eu digitei era primo ou não.

Em um determinado momento, comecei a achar muito lento para numeros muito grandes e vi que bastava parar de dividir quando chegava na metade do número (o número/2). 

se tornou bem mais rapido. Ali eu notei como faz diferença na performance do software uma boa programação.

Esse problema tem naquele curso da USP de python, bem legal!

Por essa daí, mesmo não sendo cientista da computação, eu não era demitido...

@Asvidzinski pois faz aí e mostra tua solução aqui

@mvbs haha

@ebitda você me deu uma ideia de falar de otimização do algoritmo também. Valeu. 

Legal o desafio

@ThiagoBarros95 tenta resolver aí haha

massa. vou fazer quando chegar em casa e posto aqui :D estou numa janta e entediado kkk

@ghoul massa. Manda aí. 

Fiz em C# que é a linguagem que eu uso no trabalho. :D 

Não foquei em otimizações e procurei deixar o código o mais simples para que qualquer pessoa que o leia entenda o que o algoritmo faz.

Aqui temos uma lista que irá conter os 100 números. O código irá executar enquanto a lista não contiver 100 elementos. Para cada um deles é testado se aquele número é primo. Quando for ele é inserido na lista.

Ao final a lista dos números é apresentada.

static void Main(string[] args)
        {
            var numerosPrimos = new List<int>();
            var numero = 2;
            
            // Enquanto a lista não contiver 100 elementos
            while (numerosPrimos.Count < 100)
            {
                // Testa se o número atual é primo e quando for inclui ele na lista.
                if (IsNumeroPrimo(numero))
                {
                    numerosPrimos.Add(numero);
                }

                numero++;
            }

            Console.WriteLine("Lista dos primeiros 100 números primos:");
            for (var i = 0; i < numerosPrimos.Count; i++)
            {
                Console.WriteLine("Número #{0}: {1}", i + 1, numerosPrimos[i]);
            }
        }

        /// <summary>
        /// Verifica se o número informado é primo.
        /// </summary>
        private static bool IsNumeroPrimo(int numero)
        {
            for (int i = 2; i < numero; i++)
            {
                if (numero % i == 0)
                    return false;
            }
            return true;
        }?

Que tal?

@ghoul gostei haha a lógica que você usou pra dar match em números primos foi diferente da que eu criei pra resposta, só isso já valeu. E o código tá massa, mesmo eu não manjando muito de C# deu pra entender bem. Tem partes que a sintaxe lembra JavaScript e outras lembra TypeScript. 

Depois se liga na resposta que vou jogar aqui domingo à noite. Vou falar um pouco além da lógica do algoritmo. Criei umas coisas aqui pra medir o tempo do programa e umas comparações de otimização do código. 

Fiz em Ruby:

Arquivo de teste: test/prime_filter_test.rb

require 'minitest/autorun'
require 'prime_number'

class PrimeNumberTest < Minitest::Test
  def test_first_ten
    assert_equal [2,3,5,7], PrimeNumber.filter( (1..10).to_a )
  end
end

Modulo com o método: lib/prime_number.rb

module PrimeNumber
  def self.filter(list)
    list.select {|number| prime?(number) }
  end

  def self.prime?(number)
    return false if number == 1

    half_num = number / 2
    half_num += 1 if number.odd?

    divisors = 1.upto(half_num)
      .select{|div| number.divmod(div)[1] == 0}
    divisors == [1]
  end
end?

Para executar o teste:

ruby -Ilib:test test/prime_filter_test.rb

Para testar usando o IRB, o REPL de ruby. Equivalente a executar pyhton no terminal:

$ irb -Ilib:test
2.6.2 :001 > require 'prime_number'
 => true 
2.6.2 :002 > PrimeNumber.filter (1..100).to_a
 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 
2.6.2 :003 > 

@ghoul minha compreensão do problema foi diferente. Eu entendi que era para receber uma lista de números e listar os que são primos.
Na tua solução, se eu entendi direito, tu lista os X primeiros números primos.

Que bom que gostou, @ThiagoDV ! :D É uma das coisas que eu gosto nessas linguagens derivadas do C, todas têm uma sintaxe muito familiar. eu rabisco alguma coisa com javascript também. já passei por Java antes do C#, e C na faculdade. difícil cair muito longe do pé. hehehe

@Abra gostei da forma como código ficou enxuto no Ruby. Apanhei pra ler esse código kkkk mas acho q entendi a essência.


@ThiagoDV eu tinha entendido diferente o enunciado. Olhando novamente agora tanto o enunciado quanto na resposta do @Abra vocês listam os números primos contidos no intervalo de 1 a 100.

Eu tinha entendido que era para listar os primeiros 100 números primos. kkkk acho que é o sono.

@Abra na verdade o problema era esse mesmo, a lista de 1 a 100 e listar os primos, mas a solução do @ghoul mesmo não recebendo essa lista inicialmente também acaba resolvendo o problema e um pouco além então tá valendo.

E eu já usei Ruby uma vez num teste de empresa mas não lembro de mais nada da sintaxe haha tá parecendo meio grego pra mim mesmo eu já tendo usado. Mas a solução é o que vale. Ainda fez uma espécie de TDD aí  show de bola. 

@ghoul era haha era pra pegar a lista inicial de 1 a 100 e capturar os primos. Mas tá valendo. Na solução eu vou resolver o problema inicial e depois disso mostrar a performance do algoritmo em listas com números de até 1 a 10000. 

Pra mim o desafio já valeu, ver as respostas da galera já valeu demais. Esperar até amanhã a noite pra ver se mais alguém resolve aí. 

@ThiagoDV @ghoul tl;dr: eu tento escrever a interface dos métodos o mais legível possível.
Daí que se você tentar ler em voz alta o código, pra mim, fica mais claro.

P.S.: fiz uma versão para tratar número negativo na lista

P.S. 2: Já é a terceira vez que escrevo. Perdi as outras.

P.S. 3: select é método de array
upto é método de Integer.

Se precisar posso explicar melhor.

@Abra dando outra olhada eu acho que entendi a lógica. 

A sintaxe de Ruby é linda mas bem diferente de outras linguagens que já vi por aí. Enquanto o código do Ghoul em C#eu entendi rapidamente, o em Ruby eu demorei mais por não saber de detalhes da linguagem como os métodos de inteiros.