Executando verificação de segurança...
1

Para calcular números primos normalmente se usa um crivo de Eratóstenes, pois assim diminui o processamento, isso para quem faz faculdade na área de computação ou matemática aprende no início do curso mas na maior parte das vezes nem dá bola kk.

Na minha cadeira de Algoritmos e Programação fizemos um crivo de eratóstenes em Fortran, mas como é uma linguagem muito pouco usada e com uma sitaxe muito diferente eu quis portar o código para C, é bem legal kk.

Mas falando em Python, tem um repositório no github que tem muitos algorítmos feitos em python, lá temos algorítmos de cálculo de sequência de fibonacci, de criptografia, estruturas de dados e também o crivo de Eratóstenes.

link do repositório: https://github.com/AllAlgorithms/python/tre
Crivo de Eratóstenes em Python

Vou colocar também o crivo de Eratóstenes feito em Fortran, porque implementa o crivo de uma maneira um pouco diferente da abordagem feita no repositório que citei, mas vou colocar ele implementado em Python porque ninguém merece ter que interpretar código de Fortran 95 kk.

(onde estiver '>' leia como 'maior que' e onde estiver '<' leia como 'menor que', isso é devido a um bug reportado [aqui]

import math

def erathostenes_sieve(n: int):
    if n < 2:
        raise ValueError('The value must be bigger or equal to 2')
    if n == 2:
        return [2]

    aux = [ True for _ in range(n) ]
    
    lim = math.floor(math.sqrt(n))
    
    for i in range(2, lim):
        if aux[i]:
            for k in range(n):
                j = i * (i + k)
                if j >= n:
                    aux[-1] = False
                    break
                else:
                    aux[j] = False

    prime_numbers = []
    for i, prime_number in enumerate(aux):
        if prime_number:
            prime_numbers.append(i)

    return prime_numbers[2:]
Carregando publicação patrocinada...