Primeiro ponto a ser apreciado: 10^9
é possível ser representado com 32 bits (na real, 32 bits chega a até aproximadamente 4 bilhões), logo o limite superior da entrada (que é 10^8
) é possível de se representar em um signed long int
em C. Até onde me lembro, os compiladores mais modernos entendem o int
como sendo 32 bits e sinalizado. Então não precisamos fazer grandes ginásticas com a representação. C também aceita colocar simplesmente long
para esse tipo.
Depois, qual o limite máximo para procurar o primo? Bem, como o número é composto pela soma de quadrados, isso significa que qualquer número maior que 10^4
gerará um quadrado maior do que 10^8
. Portanto, o limite máximo é 10^4
: se chegou nesse limite, posso cancelar a busca por novos números primos.
Não posso usar funções, mas posso começar a rascunhar com elas para depois fazer o processo de "abri-las" dentro do código. Isso ajuda a organizar as ideias, mas não é estritamente necessário fazer assim.
Como ficaria o código então? A ideia é buscar sempre do começo (os p1
, p2
, p3
e p4
iniciais apresentados em seu código). Se você chegar no número máximo (com o maior primo indo para algo além de 10^4
), a busca falhou. Se a soma dos primos for maior do que o número apresentado, também falhou a busca. Se a soma ficar abaixo do número procurado, então dispensamos o menor dos primos (p1
), rotacionamos os outros 3 uma "posição" menos significativa e, em cima do novo p3
, procuramos o "próximo primo".
De modo geral, seria algo assim (não vou considerar ainda a otimização da soma ser maior que o número passado):
'''
Retornamos o próximo primo ou -1 caso não seja possível definir o próximo primo,
se ele for além do limite máximo
'''
def proximo_primo(p4_old):
# considere inteiro
next = p4_old + 2
while next < 10000:
divisor = 3
while divisor*divisor < next and next % divisor != 0:
divisor += 2
if next % divisor != 0:
return next
next += 2
return -1
def is_soma_quadrado(n):
# considere como inteiros
p1 = 2
p2 = 3
p3 = 5
p4 = 7
# enquanto o próximo primo é válido, continua tentando...
while p4 != -1:
if p1*p1 + p2*p2 + p3*p3 + p4*p4 == n:
return (p1, p2, p3, p4)
# não deu como soma destes primos consecutivos
# vamos rodar os números e tentar o próximo primo
p1, p2, p3 = p2, p3, p4
p4 = proximo_primo(p4)
# retorno para que não é possível fazer essa soma
return (-1, -1, -1, -1)
O teste de primalidade é dado pelo seguinte trecho:
divisor = 3
while divisor*divisor < next and next % divisor != 0:
divisor += 2
if next % divisor != 0:
return next
Aqui, next
já começa com um valor sabidamente não primo, já que os valores possíveis de seus argumentos são primos e não recebe o 2 como argumento, nunca. Além disso, o próximo next
sempre é o valor anterior +2, então é impossível que next
seja par. Logo, não preciso testar a divisão por 2, por isso que começo com 3
. Salto os divisores candidatos de 2 em 2 para diminuir a quantidade de testes necessários, já que toda divisão com algum número par terá 1 como resto.
Eu tenho duas condições de paradas: a primeira é se o candidato a divisor realmente tiver resto distinto de zero (next % divisor == 0
), ou se estourou os candidatos úteis a divisor (divisor * divisor < next
). Essa segunda parte é mais ou menos equivalente a pergunta se divisor < sqrt(next)
, mas a multiplicação de inteiros é mais leve normalmente que o cálculo da raiz quadrada. Também evito considerar a igualdade porque, se por acaso divisor * divisor == next
, então já vai no outro caso de parada: next % divisor == 0
retornará falso.
Após o laço se concluir, eu faço a verificação para saber se o motivo da parada foi que se esgotaram os candidatos úteis a divisor ou se realmente o número next
é composto. Por isso que tem o if next % divisor != 0
no final: se for verdade, então next
é realmente um número primo.
Esse é o esquema geral. Para o laço, faríamos algo como o seguinte:
def laco_leitura():
while True:
n = proxima_leitura()
# aqui, -1 significa fim da leitura
if n == -1:
return
p = is_soma_quadrado(n)
if p[0] != -1:
print('É a soma de alguns primos')
else:
print('impossível representar')
Para começar, ainda neste estilo meio python de código, vamos remover retornos, break
, e funções. Aos poucos.
Primeiro, vamos desenrolar proximo_primo
para conseguir parar os laços sem usar return
(se eu desenrolasse atualmente seu conteúdo dentro de is_soma_quadrado
, o return
atuaria como break
, então não alcança o resultado desejado). Vou fazer uma troca grotesca na condição externa: colocar um ret == -1
na condição de continuação e, no lugar de usar um return
, farei uma atribuição ret = next
. Isso causará o término do laço e, no caso de o laço parar por estourar o limite máximo, ret
terá o valor de inicialização que será espertamente -1
:
'''
Retornamos o próximo primo ou -1 caso não seja possível definir o próximo primo,
se ele for além do limite máximo
'''
def proximo_primo(p4_old):
# considere inteiro
ret = -1
next = p4_old + 2
while next < 10000 and ret == -1:
divisor = 3
while divisor*divisor < next and next % divisor != 0:
divisor += 2
if next % divisor != 0:
ret = next
next += 2
return ret
Agora, vamos desenrolar essa função dentro de is_soma_quadrado
? Para tal, lembrando aqui que em C (mesmo no ANSI), você pode declarar variável em começo de bloco de código, então vou usar isso a nosso favor. Para tal, vou fazer a atribuição a p4
apenas no último passo, quando return ret
é chamado. O fato de que o nome das variáveis não oferece conflito torna mais fácil lidar com isso. Como o valor da variável passada como parâmetro é de apenas leitura, posso colocar diretamente p4
onde no código se tem menção a p4_old
:
def is_soma_quadrado(n):
# considere como inteiros
p1 = 2
p2 = 3
p3 = 5
p4 = 7
# enquanto o próximo primo é válido, continua tentando...
while p4 != -1:
if p1*p1 + p2*p2 + p3*p3 + p4*p4 == n:
return (p1, p2, p3, p4)
# não deu como soma destes primos consecutivos
# vamos rodar os números e tentar o próximo primo
p1, p2, p3 = p2, p3, p4
# fazendo aqui o desenrolar da função proximo_primo
# começo do bloco equivalente à chamada a proximo_primo
# considere inteiro
ret = -1
next = p4 + 2
while next < 10000 and ret == -1:
divisor = 3
while divisor*divisor < next and next % divisor != 0:
divisor += 2
if next % divisor != 0:
ret = next
next += 2
p4 = ret
# fim do bloco equivalente à chamada a proximo_primo
# retorno para que não é possível fazer essa soma
return (-1, -1, -1, -1)
Agora, desenrolar o return
prematuro. Vou usar uma estratégia semelhante à anterior, mas aqui o valor padrão será p = (-1, -1, -1, -1)
e a condição de continuar no laço é que p[0] == -1
. Também vou colocar no else
o caso em que não o número não é a soma dos atuais primos:
def is_soma_quadrado(n):
p = (-1, -1, -1, -1)
# considere como inteiros
p1 = 2
p2 = 3
p3 = 5
p4 = 7
# enquanto o próximo primo é válido, continua tentando...
while p[0] == -1 and p4 != -1:
if p1*p1 + p2*p2 + p3*p3 + p4*p4 == n:
p = (p1, p2, p3, p4)
# não deu como soma destes primos consecutivos
# vamos rodar os números e tentar o próximo primo
else:
p1, p2, p3 = p2, p3, p4
# fazendo aqui o desenrolar da função proximo_primo
# começo do bloco equivalente à chamada a proximo_primo
# considere inteiro
ret = -1
next = p4 + 2
while next < 10000 and ret == -1:
divisor = 3
while divisor*divisor < next and next % divisor != 0:
divisor += 2
if next % divisor != 0:
ret = next
next += 2
p4 = ret
# fim do bloco equivalente à chamada a proximo_primo
# retorno para que não é possível fazer essa soma
return p
Para desenrolar esta função no laço de leitura é mais fácil ainda: quase que apenas copiar e colar diretamente. A única diferença aqui é que, no lugar de usar um retorno tradicional, vou preencher diretamente a variável p
(também vou aproveitar e trocar o laço infinito por um que é finitamente conhecido:
def laco_leitura():
devemos_continuar = True
while devemos_continuar:
n = proxima_leitura()
# aqui, -1 significa fim da leitura
if n == -1:
devemos_continuar = false
else:
# bloco que determina se o número é soma dos quadrados de 4 primos consecutivos
p = (-1, -1, -1, -1)
# considere como inteiros
p1 = 2
p2 = 3
p3 = 5
p4 = 7
# enquanto o próximo primo é válido, continua tentando...
while p[0] == -1 and p4 != -1:
if p1*p1 + p2*p2 + p3*p3 + p4*p4 == n:
p = (p1, p2, p3, p4)
# não deu como soma destes primos consecutivos
# vamos rodar os números e tentar o próximo primo
else:
p1, p2, p3 = p2, p3, p4
# fazendo aqui o desenrolar da função proximo_primo
# começo do bloco equivalente à chamada a proximo_primo
# considere inteiro
ret = -1
next = p4 + 2
while next < 10000 and ret == -1:
divisor = 3
while divisor*divisor < next and next % divisor != 0:
divisor += 2
if next % divisor != 0:
ret = next
next += 2
p4 = ret
# fim do bloco equivalente à chamada a proximo_primo
# fim do bloco que determina se o número é soma dos quadrados de 4 primos consecutivos
if p[0] != -1:
print('É a soma de alguns primos')
else:
print('impossível representar')
Agora eu poderia eliminar totalmente a variável p
, mas acho que não será necessário. Transpondo para c, a primeira coisa que faria seria trocar o while
advindo de proximo_primo
para um for
clássico:
- inicia com
divisor = 3
- a condição é
divisor*divisor < next && next % divisor != 0
- o incremento é
divisor += 2
Assim, o corpo do laço continua basicamente vazio. Preciso tomar o cuidado de não perder a referência a divisor
e sair do escopo. Logo, divisor
precisaria ser declardo fora do bloco de inicialização do for
. Além disso, ainda tenho desafios com 2 pontos:
- me livrar da tupla
p
- tratar a leitura
Como está na questão
A sequencia só funciona para a primeira entrada, e depois simplesmente apaga
eu estou aqui supondo que sejam fornecidas várias entradas para a mesma execução. Então, como saber que terminou a leitura? O padrão na maioria das questões que eu costumo ver é ter uma entrada de parada, mas isso não está descrito aqui. Tem um ou outro canto que o fim da entrada é indicada pelo EOF
da stdin
, e assim eu irei tratar aqui.
Para tal, a leitura continua sendo usando scanf("%d", &n)
, mas eu guardarei a saída de scanf
. Segundo a documentação (ok, eu sei que é do C++, mas nesse ponto em específico o C++ foi desenhado pra ser totalmente parte compatível), se não conseguiu ler nada, será emitido um EOF
como saída. Logo, só verificar se retornou EOF
ou continuar o processamento feliz. Vou fazer isso da forma mais travessa possível: criar uma variável para indicar que atingiu EOF
começando com verdade, atualizá-la com a saída da leitura do scanf
e verificar, tanto no laço como antes de fazer qualquer computação (na prática simulando um break
de um laço infinito), seu valor:
int devemos_continuar = 1;
long n;
while (devemos_continuar) {
devemos_continuar = scanf("%ld", &n) != EOF;
if (devemos_continuar ) {
...
}
}
Assim tratamos a leitura. Só nos falta nos livrar de p
. Para nos livrar dela, vou usar de p1, p2, p3, p4
para servir como "portadoras" dos valores das posições da tupla. Assim, preciso tomar o cuidado para, quando for o caso de dar um retorno de algo ruim, tratar corretamente isso:
int devemos_continuar = 1;
long n;
while (devemos_continuar) {
devemos_continuar = scanf("%ld", &n) != EOF;
if (devemos_continuar) {
// grossamente equivalente ao "p = (-1, -1, -1, -1)"
long prim1 = -1, prim2 = -1, prim3 = -1, prim4 = -1;
{
// bloco que determina se o número é soma dos quadrados de 4 primos consecutivos
long p1 = 2, p2 = 3, p3 = 5, p4 = 7;
// enquanto o próximo primo é válido, continua tentando...
while (prim1 == -1 && p4 != -1) {
if (p1*p1 + p2*p2 + p3*p3 + p4*p4 == n) {
// grossamente equivalente ao "p = (p1, p2, p3, p4)"
prim1 = p1;
prim2 = p2;
prim3 = p3;
prim4 = p4;
} else {
// não deu como soma destes primos consecutivos
// vamos rodar os números e tentar o próximo primo
p1 = p2;
p2 = p3;
p3 = p4;
// fazendo aqui o desenrolar da função proximo_primo
// começo do bloco equivalente à chamada a proximo_primo
{
long ret = -1;
long next = p4 + 2;
while (next < 10000 && ret == -1) {
long divisor;
for (divisor = 3; divisor*divisor < next && next % divisor != 0; divisor += 2);
if (next % divisor != 0) {
ret = next;
}
next += 2;
}
p4 = ret
}
}
}
}
if (prim1 != -1) {
printf("É a soma de alguns primos\n");
} else {
printf("impossível representar\n");
}
}
}
Podemos melhorar a performance para o caso de negativos: impedir que se tente continuar calculando quando a soma é maior do que o número passado. Para tal, onde temos
...
while (prim1 == -1 && p4 != -1) {
if (p1*p1 + p2*p2 + p3*p3 + p4*p4 == n) {
...
vamos colocar a soma menor que ou igual a o número passado no começo do laço, e só a atualizando no final do while
:
long soma = p1*p1 + p2*p2 + p3*p3 + p4*p4;
...
while (prim1 == -1 && p4 != -1 && soma <= n) {
if (soma == n) {
...
}
// ... acha o novo p4 e chega no final do while ...
soma = p1*p1 + p2*p2 + p3*p3 + p4*p4;
}
...
Veja funcionando no IDEOne.
Para se adequar a formatação da saída, precisamos apenas imprimir usando os valores de prim1
, prim2
, prim3
e prim4
. Segue abaixo código completinho:
#include <stdio.h>
int main() {
int devemos_continuar = 1;
long n;
while (devemos_continuar) {
devemos_continuar = scanf("%ld", &n) != EOF;
if (devemos_continuar) {
// grossamente equivalente ao "p = (-1, -1, -1, -1)"
long prim1 = -1, prim2 = -1, prim3 = -1, prim4 = -1;
{
// bloco que determina se o número é soma dos quadrados de 4 primos consecutivos
long p1 = 2, p2 = 3, p3 = 5, p4 = 7;
long soma = p1*p1 + p2*p2 + p3*p3 + p4*p4;
// enquanto o próximo primo é válido, continua tentando...
while (prim1 == -1 && p4 != -1 && soma <= n) {
if (soma == n) {
// grossamente equivalente ao "p = (p1, p2, p3, p4)"
prim1 = p1;
prim2 = p2;
prim3 = p3;
prim4 = p4;
} else {
// não deu como soma destes primos consecutivos
// vamos rodar os números e tentar o próximo primo
p1 = p2;
p2 = p3;
p3 = p4;
// fazendo aqui o desenrolar da função proximo_primo
// começo do bloco equivalente à chamada a proximo_primo
{
long ret = -1;
long next = p4 + 2;
while (next < 10000 && ret == -1) {
long divisor;
for (divisor = 3; divisor*divisor < next && next % divisor != 0; divisor += 2);
if (next % divisor != 0) {
ret = next;
}
next += 2;
}
p4 = ret;
}
}
soma = p1*p1 + p2*p2 + p3*p3 + p4*p4;
}
}
if (prim1 != -1) {
printf("%ldˆ2 + %ldˆ2 + %ldˆ2 + %ldˆ2\n", prim1, prim2, prim3, prim4);
} else {
printf("Impossivel a representacao\n");
}
}
}
return 0;
}