DEV Community

Cover image for Quais são os números primos de 1 a 1.000.000?
Fabiano Santos Florentino
Fabiano Santos Florentino

Posted on • Updated on

Quais são os números primos de 1 a 1.000.000?

Números primos são números naturais maiores que 1 que são divisíveis apenas por 1 e por si mesmo. Em outras palavras, um número primo não pode ser escrito como um produto de dois números inteiros positivos diferentes de 1 e ele próprio.

Os números primos têm uma importância fundamental na matemática, já que muitas propriedades dos números inteiros estão relacionadas aos números primos. Eles são a base para a aritmética modular, o teorema fundamental da aritmética e muitos outros resultados importantes da teoria dos números.

Os números primos são usados em muitas aplicações práticas, como na criptografia e na geração de números aleatórios. A identificação de números primos grandes é um problema importante na matemática e em ciência da computação, existem muitos algoritmos desenvolvidos especificamente para esse propósito.

Números primos negativos?

Não, não existem números primos negativos. Os números negativos não são considerados números naturais, portanto, não podem ser considerados primos.

Os números primos resolvem qual problema na computação moderna atualmente?

Números primos são fundamentais na criptografia moderna, uma das áreas mais importantes na computação atual. São usados para garantir a segurança da comunicação e das transações online.

Na criptografia de chave pública, um algoritmo como o RSA usa números primos para gerar chaves criptográficas que são usadas para criptografar e descriptografar dados. O segredo desse algoritmo está em fatorar números primos grandes, o que é uma tarefa extremamente difícil e computacionalmente custosa.

Outra aplicação para os números primos, é na criação de hash criptográfico, que é uma função que mapeia dados de tamanho variável em um valor fixo de tamanho menor. Isso é útil para verificar a integridade dos dados e garantir que não foram modificados ou corrompidos durante uma transmissão.

Mostrar todos os números primos de 1 a 1.000.000 pode ser uma tarefa útil para fins didáticos, de aprendizado ou de verificação. Isso pode ajudar a entender melhor o conceito de números primos e como eles são distribuídos entre os números naturais inteiros.

Também pode ser útil para fins de otimização de algoritmos ou para verificar a eficiência de um algoritmo de busca de números primos.

É importante observar que gerar números primos pode ser uma tarefa demorada e computacionalmente custosa. e pode não ser necessária em todos os casos. Para muitas aplicações práticas, é suficiente gerar apenas alguns números específicos ou uma faixa limitada de números primos.

Então qual é a linguagem de programação contaria mais rápido os números primos de 1 a 1.000.000?

Golang



package main

import "fmt"

func main() {
    for i := 2; i <= 1000000; i++ {
        prime := true
        for j := 2; j*j <= i; j++ {
            if i%j == 0 {
                prime = false
                break
            }
        }
        if prime {
            fmt.Println(i)
        }
    }
}


Enter fullscreen mode Exit fullscreen mode

O programa Go acima utiliza o algoritmo de verificação de números chamado Crivo de Eratóstenes para imprimir todos os números primos de 2 até 1.000.000. É usado dois loops for aninhados
para iterar através de todos os números no intervalo e determinar se cada número é primo, e se um número for primo, ele é impresso na tela usando a função fmt.Println.

go

Ruby



(2..1000000).each do |i|
  prime = true
  (2..Math.sqrt(i)).each do |j|
    if i % j == 0
      prime = false
      break
    end
  end
  if prime
    puts i
  end
end


Enter fullscreen mode Exit fullscreen mode

Nesse programa em Ruby para efeito de comparação também é utilizado o algoritmo Crivo de Eratóstenes para imprimir todos os números primos. É utilizado dois loops each aninhados para iterar através de todos os números no intervalo determinado e validar cada número primo. Sendo um número primo, ele é impresso na tela usando a função puts.

ruby

Python



def print_primes(n):
    primes = [True] * (n+1)
    primes[0], primes[1] = False, False
    for i in range(2, int(n**0.5)+1):
        if primes[i]:
            for j in range(i*i, n+1, i):
                primes[j] = False
    for i in range(n+1):
        if primes[i]:
            print(i)

print_primes(1000000)


Enter fullscreen mode Exit fullscreen mode

python

Nessa função em Python também é utilizado o algoritmo Crivo de Eratóstenes para imprimir os números primos. É inicializado um array de booleanos, assumindo que todos os números são primos, varrendo o array a partir do número 2 e marcando todos os seus múltiplos como não primos, e por fim, imprimindo todos os números primos encontrados.

Nossa!, então Python é a melhor linguagem de programação para trabalhar com números primos?

A resposta é NÃO! definitivamente!

A velocidade na contagem de números primos de 1 a 1.000.000 em um programa depende de diversos fatores, como eficiência do algoritmo, implementação do código, velocidade do processador e quantidade de memória disponível. Por isso, não é possível afirmar como certeza qual linguagem seria mais rápida sem realizar testes e comparações entre implementações específicas.

Algumas linguagens de programação são conhecidas por serem mais rápidas em cálculos matemáticos e manipulação de números, como C, C++, Fortran e Rust, sendo frequentemente utilizadas em programação científica de alto desempenho. Por outro lado linguagens como Go, Ruby e Python são consideradas mais fáceis de usar e desenvolver, apresentando recursos poderosos para manipulação de números e cálculos matemáticos, porém podem ter desempenho inferior em comparação com linguagens de baixo nível.

A escolha da linguagem mais rápida dependerá do contexto específico do projeto, das habilidades do programador e dos requisitos de desempenho, podendo ser considerada a linguagem Go, por exemplo, por sua alta performance e eficiência mesmo que os testes acima demonstrem o Python como o mais rápido.

Deixo aqui meu agradecimento ao amigo de trabalho Helvécio Neto, esse post nasceu de um Brainstorm que tivemos no trabalho sobre eficiência computacional, vlw mano!

Top comments (0)