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).
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
# 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)