1

Gostaria que o código que escrevi me retorne uma quantidade de tuplas de acordo com o valor inserido no input, por exemplo, se o input é 3, o retorno terá que ser 3 pares de tuplas. A imagem a seguir deixará mais claro. inserir a descrição da imagem aqui

Aqui o meu código:

"""Números primos gêmeos são pares de números primos (p1, p2) tais que p2=p1+2.

Implemente uma função chamada primos_gemeos que recebe um número inteiro n e 
retorna os n primeiros pares de números primos gêmeos, conforme formatação indicada abaixo."""
def primos_gemeos(num):
  valor = False
  for n in range(2, num):
     if num % n == 0:
        break
  else:
     valor = True
  return valor

entrada = int(input())
i = 0
lista = []
while i < entrada:
  for j in range(3, entrada + 1, 2):
     if primos_gemeos(j) and primos_gemeos(j + 2):
        lista.append((j, j + 2))
        i += 1
print(lista)
    
primos_gemeos(entrada)

No meu código o que tentei fazer foi um while que repete enquanto i < entrada e incrementa 1 após o append, porém o retorno está repetindo os pares, por exemplo, quando a entrada é 3, a saída teria que ser assim: [(3, 5), (5, 7), (11, 13)] Mas na saída do meu código está sendo assim: [(3, 5), (3, 5), (3, 5)] Onde eu errei?

2 Respostas 2

2

Um dos problemas do código (e talvez o único, sem ter testado) é não estares a alterar (incrementar) o valor de j, por isso acabas sempre com os mesmos valores.

O que são Números Primos Gémeos?

Uma implementação pode ser feita assim:

def e_primo(num): # verificar se e primo
    return all(num%i!=0 for i in range(2,num)) 

qtd_tuples = 10 # input
results = [] # armazenar resultados
curr_prime = 1
while len(results) < qtd_tuples: # enquanto a quantidade de tuplas for inferior ao nosso input
    curr_prime += 2
    if(e_primo(curr_prime) and e_primo(curr_prime+2)):
        results.append((curr_prime, curr_prime+2))

print(results)

Output:

[(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109)]

DEMONSTRAÇÃO

1

Fazer um teste de mesa já faria com que você percebesse o erro: entrada é a quantidade de pares que você deve retornar, mas no for você está usando range(3, entrada + 1, 2), ou seja, esse for só verifica os números até entrada.

Portanto, quando entrada é 3, o range só vai até 3, e dentro do for, como você testa j e j + 2, nesse caso sempre estará testando apenas 3 e 5.

Então na verdade você deveria usar entrada apenas para controlar a quantidade de pares já gerados. Já os números a serem testados não devem ter limite, pois você não sabe qual o número que estará no enésimo par.

Outros pontos a melhorar é que você pode começar no 3 (pois eu sei que (2, 3) não são primos gêmeos). E o algoritmo dá para melhorar um pouco: como eu já começo excluindo o 2, não preciso testá-lo, e também não preciso testar os números pares. Além disso, a partir do 5, todos os números primos são da forma 6k - 1 ou 6k + 1 (ou seja, são antecessores ou sucessores de um múltiplo de 6), então posso verificar apenas esses valores. E o loop pode ir até a raiz quadrada do número.

Então ficaria:

from math import sqrt

# ATENÇÃO: **nesse caso específico**, como eu não testo o 2,
# estou deliberadamente ignorando ele e os demais números pares
def primo(n):
    if n == 3:
        return True
    if n % 3 == 0:
        return False

    i = 5
    limite = int(sqrt(n)) + 1
    while i < limite:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

    return True

quantidade = int(input())
lista = []
# começo no 3, pois sei que (2, 3) não são gêmeos
n = 3
while True:
    if primo(n) and primo(n + 2):
        lista.append((n, n + 2))
        if len(lista) == quantidade: # se já tenho a quantidade de pares, interrompe o while
            break
    n += 2

print(lista)

Atenção: Como eu só chamo a função primo passando números ímpares, então dentro dela eu não verifico se o número é par. Mas se fosse uma função de uso geral, para verificar se qualquer número é primo, aí teria que verificar (ficaria assim).


Só tem um detalhe: veja que no while eu testo n e n + 2.

Isso quer dizer que na primeira iteração eu testo se 3 e 5 são primos. Depois, na segunda iteração, eu testo se 5 e 7 são primos, depois eu testo 7 e 9, depois 9 e 11, etc. Repare que há vários números sendo testados 2 vezes, sem necessidade. Então você pode otimizar um pouco, fazendo com que eles sejam testados apenas uma vez, e reaproveitar esta informação na próxima iteração:

lista = []
proxPrimo = None
# começo no 3, pois sei que (2, 3) não são gêmeos
n = 3
atualPrimo = primo(n)
while True:
    proxPrimo = primo(n + 2)
    if atualPrimo and proxPrimo:
        lista.append((n, n + 2))
        if len(lista) == quantidade:
            break
    atualPrimo = proxPrimo
    n += 2

print(lista)
4
  • Muito bom. Presumo que possamos descartar também os pares logo? ideone.com/CheTnL
    – Miguel
    Commented 5/02/2021 às 14:53
  • @Miguel Nesse caso específico, como estou chamando a função primo somente para números ímpares, ignorei os pares de propósito (veja o comentário no código: "como eu não testo o 2, estou deliberadamente ignorando ele e os demais números pares". Mas para uma função de uso geral, aí sim, deveria testar se o número é par e descartar logo de cara - a única exceção é o próprio 2, então teria que ser assim: ideone.com/zlnWdd
    – hkotsubo
    Commented 5/02/2021 às 15:01
  • Ha pois claro, claro... Distração minha
    – Miguel
    Commented 5/02/2021 às 15:02
  • @Miguel De qualquer forma, editei a resposta, deixando mais claro esse ponto. Obrigado!
    – hkotsubo
    Commented 5/02/2021 às 15:04

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .