0

Estou trabalhando em um código, porém não consigo compreender o que há de errado. A sequencia só funciona para a primeira entrada, e depois simplesmente apaga. É suposto que o usuario entre com um numero qualquer (0 a 10ˆ8) e o programa retorne se aquele numero inserido pode ser representado como a soma do quadrado de 4 primos consecutivos, por exemplo:

Entrada: 87

Saída: 2ˆ2 + 3ˆ2+ 5ˆ2+7ˆ2

Entrada: 2020

Saída: 17ˆ2 + 19ˆ2 + 23ˆ2 + 29ˆ2

Entrada: 100

Saída: Não é possível a representação

Qualquer dica, agradeço imensamente.

Obs: É proibido utilizar funções, vetores, breaks e etc. É um trabalho de faculdade sobre as funções mais básicas: ifs, fors e whiles. Obrigada!

Eis o código:

#include <stdio.h>
#include <math.h>

#define true 1
#define false 0

int main() {

    int p1=2, p2=3, p3=5, p4=7, next, i, n, prime;

    printf("Entrada: ");
    scanf("%d", &n);

    while(true){
        if((p1 *p1) + (p2 *p2) + (p3 *p3) + (p4 *p4) == n){
            printf("Saida: %dˆ2 + %dˆ2 + %dˆ2 + %dˆ2", p1, p2, p3, p4);
        }
        next = p4+2;
        if(next > n)
        printf("Impossivel a representacao");
        while(true)
        for(i=3; i<= sqrt(next); i=i+2){
            if(next % i == 0)
                prime = false;
                    else{
                        prime = true;}
        }
        if(prime == true){
                p1=p2;
                p2=p3;
                p3=p4;
                p4=next;
            }
            else{
                next = next +2;}
    }

        return 0;
        }

        ```
3
  • Já respondido em: pt.stackoverflow.com/questions/441099/…
    – anonimo
    Commented 24/03/2020 às 18:34
  • @anonimo Eu vi este código, porém, como ainda estou iniciando em C, fica complicado entender o que a pessoa fez em python
    – Marcelly
    Commented 24/03/2020 às 18:37
  • Não pode usar funções nem break nem vetores? Cara, vai ser bem lento essa bagaça e chato, mas dá para fazer... Commented 24/03/2020 às 20:41

2 Respostas 2

2

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 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;
}
6
  • Meu Deus, você é um verdadeiro professor em se tratando de algoritmos!! Muitíssimo obrigada pela ajuda e pelo tempo que gastou nesse programa enorme!! É impressionante a capacidade de alguém em criar algo assim, incrível! Posso lhe fazer somente mais uma pergunta: como posso fazer para manter o programa rodando (pedindo novo N) e encerrar com uma msg qualquer quando o usuário digita 0 (zero)?
    – Marcelly
    Commented 26/03/2020 às 2:07
  • Ah, então N == 0 é o caso de parada? Ok, razoável, mas deveria estar na pergunta. Está vendo ali em cima quando eu deixo explícito o laço sobre a variável devemos_continuar? Pois bem, como a condição de parada não é o fim da entrada padrão, então não é comparando a saída do scanf com EOF, mas sim n com 0. Então é só mudar a atribuição de devemos_continuar para n != 0. Na real, como é C e qualquer coisa diferente de 0 significa verdade, bastaria usar n no lugar de devemos_continuar, mas sempre com o cuidado de garantir a primeira entrada no laço. Commented 26/03/2020 às 2:35
  • Fazer usando funções ou break/continue permite um código mais limpo Commented 26/03/2020 às 2:36
  • Vc poderia atualizar o codigo com a orientação acima? Eu tentei alterar segundo o que entendi mas todos os numeros que inseri retornaram que a representação é impossivel. :( A utilização de break/continue é proibida. Me desculpe n ter especificado no enunciado que zero era a condição de parada seguida de uma mensagem.
    – Marcelly
    Commented 26/03/2020 às 3:30
  • @Marcelly, sempre pode clicar em editar e corrigir isso. De toda sorte, não vou fazer a alteração agora, então continue trabalhando. Se for o caso descanse um pouco e retorne de cabeça limpa Commented 26/03/2020 às 3:51
0

Tente:

#include <stdio.h>
#include <math.h>

#define TRUE 1
#define FALSE 0

int main() {

    int p1=2, p2=3, p3=5, p4=7, next, i, n, prime;

    printf("Entrada: ");
    scanf("%d", &n);

    while (TRUE){
        if ((p1*p1) + (p2*p2) + (p3*p3) + (p4*p4) == n) {
            printf("Saida: %dˆ2 + %dˆ2 + %dˆ2 + %dˆ2", p1, p2, p3, p4);
            break;
        }
        next = p4 + 2;
        if (next > n) {
            printf("Impossivel a representacao");
            break;
        }
        else {
            prime = FALSE;
            while (next < n && prime == FALSE) {
                prime = TRUE;
                for (i=3; i<=sqrt(next) && prime == TRUE; i+=2) {
                    if (next % i == 0)
                        prime = FALSE;
                }
                if (prime == TRUE) {
                    p1 = p2;
                    p2 = p3;
                    p3 = p4;
                    p4 = next;
               }
                else {
                    next += 2;
                }
            }
        }
    }
    return 0;
}

Verifique se esta versão sem break serve:

#include <stdio.h>
#include <math.h>

#define TRUE 1
#define FALSE 0

int main() {

    int p1=2, p2=3, p3=5, p4=7, next=7, i, n, prime, achou=FALSE;

    printf("Entrada: ");
    scanf("%d", &n);

    do {
        if ((p1*p1) + (p2*p2) + (p3*p3) + (p4*p4) == n) {
            printf("Saida: %dˆ2 + %dˆ2 + %dˆ2 + %dˆ2", p1, p2, p3, p4);
            achou = TRUE;
        }
        else {
            next += 2;
            if (next > n) {
                printf("Impossivel a representacao");
            }
            else {
                prime = FALSE;
                while (next < n && prime == FALSE) {
                    prime = TRUE;
                    for (i=3; i<=sqrt(next) && prime == TRUE; i+=2) {
                        if (next % i == 0)
                            prime = FALSE;
                    }
                    if (prime == TRUE) {
                        p1 = p2;
                        p2 = p3;
                        p3 = p4;
                        p4 = next;
                    }
                    else {
                        next += 2;
                    }
                }
            }
        }
    } while ((next <= n) && (achou == FALSE));
    return 0;
}
6
  • Aqui funcionou exatamente com este caso de teste.
    – anonimo
    Commented 24/03/2020 às 20:57
  • Aliás, deixa quieto. Eu entendi que seriam diversas entradas no problema e que o código tratava isso. Agora percebi que viajei. Favor desconsiderar o comentário anterior Commented 24/03/2020 às 21:01
  • @anonimo Você é o cara! Me ajudou muito!!! Será que posso abusar de sua bondade e fazer mais uma pergunta? Existe a possibilidade de eu retirar os breaks e substituir por outra coisa?
    – Marcelly
    Commented 24/03/2020 às 23:19
  • @anonimo E também, onde eu posso colocar o "Impossível a representação" qdo o usuário entrar com um numero que não pode ser decomposto na sequencia de primos?
    – Marcelly
    Commented 25/03/2020 às 0:00
  • @anonimo Nao tenho como agradecer tamanha gentileza em dispor de seu tempo para ajudar-me. Muito obrigada! Só queria te perguntar uma coisa: é o meu computador ou o programa não está retornando quando o numero é impossivel de ser representado pela soma do quadrado de 4 primos consecutivos? Ele está pensando e pensando e n sai nada... Mudei aquele trecho de lugar no codigo mas o resultado é o mesmo...
    – Marcelly
    Commented 25/03/2020 às 4:46

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 .