Escreva uma função para determinar a quantidade de números primos abaixo N .

Passo 1

O enunciado pede uma função que, dado um inteiro N, determine quantos números primos existem estritamente abaixo de N. Esse problema envolve teoria de números (definição de número primo) e técnicas de otimização de busca de primos, em particular o Crivo de Eratosthenes.

Passo 2

Um número primo é um inteiro maior que 1 que só é divisível por 1 e por ele mesmo. A abordagem ingênua tenta, para cada inteiro i de 2 até N−1, testar se existe algum divisor de 2 até ⌊√i⌋. Se não encontrar nenhum divisor, i é primo.
A complexidade dessa verificação direta é O(N√N), que fica lento para N grandes. Para acelerar, usamos o Crivo de Eratosthenes, capaz de listar todos os primos menores que N em tempo aproximado O(N log log N).

Passo 3

No Crivo de Eratosthenes criamos um vetor booleano is_prime de tamanho N, inicializado como verdadeiro em todas as posições. Marcamos is_prime[0] e is_prime[1] como falso (0 e 1 não são primos). Em seguida, para cada p de 2 até ⌊√(N−1)⌋, se is_prime[p] for verdadeiro, marcamos todos os múltiplos de p (começando em p²) como falso.

Passo 4

Após completar o crivo, o número de primos abaixo de N é simplesmente a soma dos valores verdadeiros em is_prime para índices de 2 até N−1.

Resposta

Aqui está uma implementação em Python da função que conta primos abaixo de N usando o Crivo de Eratosthenes:
def conta_primos(N):
# Inicializa vetor de primalidade
is_prime = [True] * N
if N > 0:
is_prime[0] = False
if N > 1:
is_prime[1] = False
# Marca múltiplos de cada p
p = 2
while p * p < N:
    if is_prime[p]:
        for multiple in range(p * p, N, p):
            is_prime[multiple] = False
    p += 1

# Conta quantos permaneceram como True
return sum(is_prime)

Exercícios relacionados