Skip to main content
removeu 8 caracteres do conteúdo
Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

Primeiro ponto a ser apreciado: 10^9 é possível ser representado com 32 bits (na real, poderia 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.

Primeiro ponto a ser apreciado: 10^9 é possível ser representado com 32 bits (na real, poderia 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.

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.

Fonte Link
Jefferson Quesado
  • 23,5mil
  • 6
  • 60
  • 158

Primeiro ponto a ser apreciado: 10^9 é possível ser representado com 32 bits (na real, poderia 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 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 , 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;
}