1 min de leitura ·

O Problema dos números primos na programação

Vocês já criaram um programa que retorne uma lista de números primos do tamanho que o usuário desejar?

Matemáticamente falando, há infinitos números primos, e além disso, eles não seguem uma ordem (por enquanto, ainda não provada, como a hipótese de riemann) então

Como vocês fariam um programa eficiente que peça um tamanho da lista de números primos, e retorne a lista somente com os números primos?

Eu já fiz algo assim com Python, porém, ficou um programa extremamente pesado, e quando o número da lista era grande demais, o programa simplesmente travava.

GabrielSozinho

2 anos atrás

Eu ainda não sou tão familiarizado com JavaScript, mas eu fiz um código e ficou assim, acho que dá pra entender:

function isPrime(num) {
    for (var i = 2; i < num; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}

function printPrimeNumbers(size) {
    var primesList = [];
    var numberToVerify = 2;
    while (primesList.length < size) {
        if (isPrime(numberToVerify)) {
            primesList.push(numberToVerify);
        }
        numberToVerify++;
    }
    console.log(primesList)
}

Provavelmente esse código não está seguindo as boas práticas, mas é funcional (na minha máquina rodou 😅). E é natural que quando o número da lista é grande demais demore, computadores têm limites também.

edit: ué, o TabNews não está mostrando o sinal de < (<), só pra mim que está assim? No preview ele mostra, só não mostra no comentário mesmo.

joelcarneiro

Autor

2 anos atrás

Com base no teu código eu fiz em python:

def is_prime(number):
    for i in range(2, number, 1):
        if number % i  == 0:
            return False
    return True


def print_list_primes(list_len: int):
    result = list()
    for i in range(2, list_len, 1):
        if is_prime(i):
            result.append(i)
        else:
            pass
    print(result)

GabrielSozinho

2 anos atrás

Que massa! Mas assim ele mostra todos os números primos até número que você forneceu, certo? Testei aqui com 50 e ele me retornou os 15 números primos menores que 50.

Então entendi a proposta de forma errada, no código que eu fiz ele mostra os x primeiros números primos, onde x é o número fornecido.

gabrielTapes

2 anos atrás

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:]