Number represented as sum of square of consecutive primes in C

Asked

Viewed 326 times

0

I’m working on a code, but I can’t figure out what’s wrong. The sequence only works for the first input, and then simply erases. The user is supposed to enter any number (0 to 10ˆ8) and the program returns if that number entered can be represented as the sum of the square of 4 consecutive primes, for example:

Entree: 87

Exit: 2ˆ2 + 3ˆ2+ 5ˆ2+7ˆ2

Entree: 2020

Exit: 17ˆ2 + 19ˆ2 + 23ˆ2 + 29ˆ2

Entree: 100

Exit: It is not possible to represent

Any hint, thank you immensely.

Note: It is forbidden to use functions, vectors, breaks and etc. It is a college job on the most basic functions: ifs, Fors and whiles. Thank you!

Here’s the code:

#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;
        }

        ```
c

  • Already answered in: https://answall.com/questions/441099/verifi-se-n%C3%bamero-%C3%A9-equals-%C3%A0-sum-of-the-squares-of-4%C3%bameros-primes-consecutive/441126

  • @anonimo I saw this code, however, as I am still starting in C, it is difficult to understand what the person did in python

  • Can’t use functions neither break nor vectors? Dude, it’s gonna be really slow and boring, but you can do it...

2 answers

2

First point to be considered: 10^9 it is possible to be represented with 32 bits (in real, 32 bits reaches up to approximately 4 billion), so the upper limit of the input (which is 10^8) it is possible to be represented in a signed long int in C. As far as I can remember, the most modern compilers understand the int as being 32 bits and flagged. So we don’t need to do big gymnastics with the representation. C also accepts simply putting long for that guy.

Then, what is the maximum limit for finding the prime? Well, since the number is composed by the sum of squares, it means that any number greater than 10^4 will generate a larger square than 10^8. Therefore, the maximum limit is 10^4: if you’ve reached that limit, I can cancel the search for new prime numbers.

I can’t use functions, but I can start sketching with them and then do the process of "opening" them within the code. This helps to organize ideas, but it is not strictly necessary to do so.

What would the code look like then? The idea is to always seek from the beginning (the p1, p2, p3 and p4 initials presented in your code). If you reach the maximum number (with the largest prime going to something other than 10^4), the search failed. If the sum of the primes is greater than the number shown, the search also failed. If the sum falls below the number sought, then we dispense with the lesser of the cousins (p1), rotate the other 3 a less significant "position" and on top of the new p3, We’re looking for the "next cousin".

In general, it would be something like this (I won’t consider yet the optimization of the sum to be greater than the past number):

'''
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)

The primality test is given by the following:

divisor = 3
while divisor*divisor < next and next % divisor != 0:
  divisor += 2
if next % divisor != 0:
  return next

Here, next already starts with a value known not to be prime, since the possible values of its arguments are prime and do not receive 2 as argument, never. Besides, the next one next always is the previous value +2, so it is impossible that next be even. Therefore, I don’t need to test the division by 2, which is why I start with 3. Jump the candidate dividers of 2 in 2 to decrease the amount of tests required, since every division with some even number will have 1 as rest.

I have two conditions of stops: the first is if the divisor candidate really has distinct rest of zero (next % divisor == 0), or if it has burst useful divisor candidates (divisor * divisor < next). This second part is more or less equivalent to the question whether divisor < sqrt(next), but the multiplication of integers is usually lighter than the calculation of the square root. I also avoid considering equality because, if by chance divisor * divisor == next, So you’re on to the next stop: next % divisor == 0 will return false.

After the loop is completed, I do the checking to see if the reason for the stop was that they ran out of useful candidates to split or if really the number next is composed. Why it has the if next % divisor != 0 in the end: if true, then next is really a prime number.

This is the general scheme. For the loop, we would do something like the following:

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')

For starters, still in this kind of style code, we will remove returns, break, and functions. Gradually.

First, let’s unroll proximo_primo to stop the ties without using return (if I actually unfold its content within is_soma_quadrado, the return act as break, then does not achieve the desired result). I will make a grotesque exchange in the external condition: put a ret == -1 on condition of continuation and instead of using a return, I’ll make an assignment ret = next. This will cause the loop to end and, in case the loop stops for breaking the maximum limit, ret will have the boot value that will be smart -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

Now, let’s unroll that function within is_soma_quadrado? To do so, remembering here that in C (even in ANSI), you can declare variable at the beginning of block code, so I will use this in our favor. To that end, I will be assigning p4 only in the last step, when return ret is called. The fact that the name of the variables does not offer conflict makes it easier to deal with it. Since the value of the variable passed as parameter is read-only, I can put directly p4 where in the Code 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)

Now, unwind the return premature. I will use a strategy similar to the previous one, but here the default value will be p = (-1, -1, -1, -1) and the condition to continue in the loop is that p[0] == -1. I’ll also put in the else the case where the number is not the sum of the current primes:

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

To unwind this function in the read loop is even easier: almost just copy and paste directly. The only difference here is that, instead of using a traditional return, I will directly populate the variable p (I will also take advantage and exchange the infinite loop for one that is finitely known:

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')

Now I could totally eliminate the variable p, but I don’t think that will be necessary. Transposing to , the first thing I would do is change the while stemming from proximo_primo for a for classic:

  • begins with divisor = 3
  • the condition is divisor*divisor < next && next % divisor != 0
  • the increment is divisor += 2

Thus, the loop body remains basically empty. I need to take care not to lose the reference to divisor and go out of scope. Soon, divisor would need to be declared out of of the boot block for. Besides, I still have challenges with 2 points:

  • get rid of the tuple p
  • treat reading

As it stands in the question

The sequence only works for the first input, and then simply deletes

I am here assuming that several entries are provided for the same execution. So, how do I know you have finished reading? The pattern in most of the questions I usually see is to have a stop entry, but that’s not described here. Has either corner that the end of the input is indicated by the EOF of stdin, and so I will treat here.

For this, the reading continues to be using scanf("%d", &n), but I’ll guard the exit from scanf. According to the documentation (Okay, I know it’s C++, but at this particular point C++ was designed to be fully compatible part), if you couldn’t read anything, a EOF as output. So just check if returned EOF or continue happy processing. I will do this as mischievously as possible: create a variable to indicate that you have reached EOF starting with truth, update it with the output of the scanf and check both in the loop and before doing any computation (in practice simulating a break of an infinite loop), its value:

int devemos_continuar = 1;
long n;
while (devemos_continuar) {
  devemos_continuar = scanf("%ld", &n) != EOF;
  if (devemos_continuar ) {
    ...
  }
}

This is how we treat reading. All that remains is to get rid of p. To get rid of her, I’m gonna use p1, p2, p3, p4 to serve as "bearers" of the values of the tuple positions. Thus, I need to take care to, when it is the case to give a return of something bad, treat it correctly:

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");
    }
  }
}

We can improve performance in case of negatives: prevent you from trying to continue calculating when the sum is greater than the past number. So where do we have

...
while (prim1 == -1 && p4 != -1) {
  if (p1*p1 + p2*p2 + p3*p3 + p4*p4 == n) {
...

we will put the sum less than or equal to the number passed at the beginning of the loop, and only updating it at the end of the 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;
}
...

See working on Ideone.

To fit the output formatting, we just need to print using the values of prim1, prim2, prim3 and prim4. Follow below full code:

#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;
}

  • My God, you are a true teacher when it comes to algorithms!! Thank you so much for your help and for the time you have spent on this huge program!! It’s amazing someone’s ability to create something like this, amazing! I can ask you just one more question: how can I keep the program running (asking new N) and end with any msg when the user type 0 (zero)?

  • Ah, so N == 0 is the case of stopping? Ok, reasonable, but should be in the question. You see up there when I make explicit the loop on the variable devemos_continuar? Well, since the stopping condition is not the end of the standard input, then it is not comparing the output of the scanf with EOF, but yes n with 0. So just change the assignment of devemos_continuar for n != 0. In fact, since it’s C and anything other than 0 means truth, just use n in place of devemos_continuar, but always with the care of ensuring the first entry in the loop.

  • Do using functions or break/continue allows for cleaner code

  • Could you update the code with the guidance above? I tried to change according to what I understood but all the numbers I entered returned that the representation is impossible. : ( The use of break/continue is prohibited. I am sorry I have not specified in the statement that zero was the stop condition followed by a message.

  • @Marcelly, you can always click edit and fix it. Luckily, I won’t make the change now, so keep working. If that’s the case get some rest and come back with a clear head

  • Okay. Thanks for your help.

Show 1 more comment

0

Try:

#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;
}

Check this version without break serves:

#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;
}

  • Here it worked exactly with this test case.

  • By the way, leave it alone. I understood that there would be several entries in the problem and that the code treated this. I now realized that I traveled. Please disregard the previous comment

  • @anonimo You are the guy! You helped me a lot!!! Could I abuse your kindness and ask one more question? There is a possibility that I will remove the breaks and replace them with something else?

  • @anonimo And also, where I can put the "Impossible representation" when the user enters a number that cannot be decomposed in the sequence of primes?

  • @anonimo I can’t thank you enough for taking the time to help me. Thank you! I just wanted to ask you one thing: is my computer or is the program not returning when the number is impossible to be represented by the square sum of 4 consecutive primes? He is thinking and thinking and nothing comes out... I changed that part of the code but the result is the same...

  • Really missing a change: initialize variable next with 7 and replace: next = p4 + 2; for next += 2;. Corrected.

Show 1 more comment

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.