Check if number is equal to the sum of squares of 4 consecutive prime numbers

Question

I need to do a program where I type a number and the program checks if it is the sum of the square of 4 consecutive primes.

Example: 2020 has to give 17 2 + 19 2 + 23 2 + 29 2

My code for now is like this:

n = int(input("n: "))
num = 2
cont = 0
for div in range(1, num + 1):
    if num % div == 0:
        cont = cont + 1
    num = num + 1
if cont == 2:
    nprimo = True
else:
    nprimo = False
p = 0
while p < n and nprimo:
    n = (num ** 2) + ((num + 1) ** 2) + ((num + 2) ** 2) + ((num + 3) ** 2)

I think the part about checking if the number is prime is correct, the problem is at the end, all the numbers are false. Does anyone have any idea?

Answer 1

If you make a site search will find several different algorithms to determine if a number is prime (if you search in Google then you will find many others, and you will see that your algorithm is very far from correct).

But even if it was right, in the end you add up num ** 2 with (num + 1) ** 2, and that’s already wrong. If num for cousin, then num + 1 will only be cousin if num is equal to 2. For any other prime number, num + 1 will be an even number (and therefore divisible by 2, and therefore will not be prime). The same goes for num + 2 and num + 3, at least one of them will not be cousin.

There is actually no fixed interval between prime numbers. Given any prime number, the next prime number may be at any distance ahead (on this assumption I suggest a read here), then there is no way to add 1 (or any other fixed value) and surely find another prime number. The way is to calculate it even.

---

^{In this comment you said you can’t use lists or functions (which is a restriction that should be in the question, so people do not waste time writing answers that do not serve can focus on the most appropriate solution for your case).}

Without using lists or functions, a solution would be to store 4 consecutive prime numbers in variables and check whether the sum of their squares is equal to the number in question. If it’s not, I calculate the next prime number, add it up again, and so on.

import math
n = int(input("n: "))

# já inicio com os 4 primeiros primos
p1, p2, p3, p4 = 2, 3, 5, 7
while True:
    if (p1 ** 2) + (p2 ** 2) + (p3 ** 2) + (p4 ** 2) == n:
        print(f'Encontrei: {p1}, {p2}, {p3} e {p4}')
        break # encontrei, sai do loop

    # não encontrei, buscar o próximo primo
    proximo = p4 + 2 # posso começar a partir de p4
    while proximo <= n: # loop para verificar se "proximo" é primo
        # loop pode ir até raiz quadrada do número: https://stackoverflow.com/q/5811151 
        # range de 2 em 2, para só testar números ímpares
        # como "proximo" é ímpar, não preciso começar o range em 2, pode começar direto no 3
        for i in range(3, int(math.sqrt(proximo) + 1), 2):
            if proximo % i == 0:
                primo = False
                break # "proximo" não é primo, sai do for
        else: # se o for não for interrompido pelo break, cai nesse else
            primo = True

        if primo: # atualiza a lista de primos e sai do while interno (volta para o while externo, que verifica a soma dos quadrados)
            p1, p2, p3, p4 = p2, p3, p4, proximo
            break
        else: # não é primo, tentar o próximo número ímpar
            proximo += 2

    if proximo > n: # se já passou de n, é porque não tem
        print(f'{n} não é igual a soma de 4 primos consecutivos ao quadrado')
        break # sai do loop

---

If you could use lists, an alternative would be to have a list of all the cousins n, and then go through it doing the checking (as did the another answer, for example).

The algorithm below has been removed of this answer, and is an implementation of Sieve of Eratosthenes:

import math
n = int(input("n: "))

# criar lista com todos os primos até n (algoritmo do Crivo de Eratóstenes)
primos = list(range(2, n))
for i in range(2, int(math.sqrt(n) + 1)):
  if i in primos:
    for j in range(i ** 2, n, i):
      if j in primos:
        primos.remove(j)

# verificar a soma dos quadrados
for i in range(len(primos) - 3):
    if (primos[i] ** 2) + (primos[i + 1] ** 2) + (primos[i + 2] ** 2) + (primos[i + 3] ** 2) == n:
        print(f'Encontrei: {primos[i]}, {primos[i + 1]}, {primos[i + 2]} e {primos[i + 3]}')
        break # encontrei, sai do loop
else:
    print(f'{n} não é igual a soma de 4 primos consecutivos ao quadrado')

Of course you can optimize, because you don’t need to create the list with all the cousins until n, could go to the square root of n divided by 2, among other details. But for an exercise, it should be enough.

Answer 2

Try:

def ehprimo(num,primos):
    for divi in primos:
        if num%divi == 0:
            return False
    return True

num,cont,primos = 2,1,[]
while cont <= 100000:
    if ehprimo(num,primos) == True:
        cont += 1
        print(num)
        primos.append(num)
    num += 1
n = int(input("Informe um número: "))
i = 0
while i < len(primos)-3:
    if n == (primos[i]**2 + primos[i+1]**2 + primos[i+2]**2 + primos[i+3]**2):
        print(n, " = ", primos[i], "^2 + ", primos[i+1], "^2 + ", primos[i+2], "^2 + ", primos[i+3], "^2")
        break
    i += 1