Trouble finding prime numbers

Question

Today in college I learned about the for and the while. However, the code I am trying to formulate does not run. It compiles but "Buga" after it puts the value. The code is simply for checking whether the number is prime or not.

#include <windows.h>
#include <stdio.h>

int main(void)
{
        int a,b,i;
        printf("Entre com o numero para saber se e primo");
        scanf ("%d", &a);
        i=a;
        while (i>1){
            b=a/(i-1);
            i=i-1;
                if (a%(i-1)==0){
                     printf ("Nao Primo");
                }else
                     printf ("Primo");
        }
        system ("Pause");
}

Answer 1

The problem is that as you decrease the value of i, one hour it will be worth 1 and you will be dividing a by 0:

b = a / (1-1);

Simplifying your logic, you could create a function that checks whether a number is prime or not in a more direct way:

#include <windows.h>
#include <stdio.h>
#include <stdbool.h>

bool TestePrimo(int a)
{
    int i;
    for (i = 2; i < a; i++) 
    {
        if (a % i == 0 && i != a) //Se o número é divisível por outro número que não seja ele mesmo, ele não é primo.
            return false;
    }

    return true; //Se nenhum teste do laço retornou valor, então o número é primo.
}

int main(void)
{
    int a;
    printf("Entre com o numero para saber se e primo");
    scanf ("%d", &a);

    if (TestePrimo(a))
       printf("Primo");
    else
       printf("Nao primo");

    system ("pause");
}

Taking advantage of the notes of mgibsonbr, the use of break would be interesting to keep checking within the function main:

int i;
bool verifica = true; //Variável booleana que indicará se o número é primo (true) ou não (false).
for (i = 2; i < a; i++) 
{
    if (a % i == 0 && i != a)
    {
        verifica = false;
        break; //Sair do laço pois um divisor do número já foi encontrado, comprovando que ele não é primo.
    }
}

if(verifica == false)
   printf("Nao primo");
else
   printf("Primo");

Answer 2

Let’s see what happens with an example

                                      // a b i
scanf("%d", &a);                      // 3
i = a;                                // 3   3
while (i > 1){                        // OK
    b = a / (i - 1);                  // 3 1 3
    i = i - 1;                        // 3 1 2
    if (a % (i - 1) == 0){            // o resto da divisao de 3 por 1 = 0
        printf("Nao primo");          // OOPS
while (i > 1){                        // OK
    b = a / (i - 1);                  // 3 1 3
    i = i - 1;                        // 3 1 1
    if (a % (i - 1) == 0){            // o resto da divisao de 3 por 0 da erro

Answer 3

Your problem, as the other answers pointed out, is that you’re subtracting 1 of i and afterward doing an operation involving i - 1. The most direct way to solve is by moving the decrease of i towards the end:

    while (i>1){
        b=a/(i-1);
        //i=i-1;                    // <-- Sai daqui...
        if (a%(i-1)==0){
             printf ("Nao Primo");
        }else
             printf ("Primo");
        i=i-1;                      // <-- ...e vem pra cá.
    }

I would also suggest stopping at 2 instead of the 1, because otherwise you will eventually a % 1 which is always 0 (I mean, the show will say that every number is "Not prime").

Besides, there are two other "weird" things in your code:

1. Every test the program will print "Primo" or "Nao Primo". If you test with 6 for example the output will be:

   Primo
   Primo
   Nao primo
   Nao primo
   Primo
   

   Instead, put in a variable whether the number is prime or not, and only print the result at the end of the test:

   int primo = 1; // Na falta de informação em contrário, todo número é primo
   i=a;
   while (i>2){
       b=a/(i-1);
       if (a%(i-1)==0){
            primo = 0; // Agora sabemos com certeza que não é primo
       }
       // Não precisa do else, se não achamos um divisor ele continua como está
       i=i-1;
   }
   if (primo == 0){
        printf ("Nao Primo");
   }else
        printf ("Primo");
   

2. The variable b is never used, so what do you need it for? It can be removed.

Other than that, there is the use of break - that maybe you haven’t learned yet. Spoiler: it serves to stop a loop earlier. If inside the if you put an additional instruction - break; - So now that he knows for sure that the number isn’t prime he doesn’t need to keep testing, he stops right there. There is also a way to stop earlier without using the break:

while (i>2 && primo != 0){

That is, only continue if the i is greater than 2 And the number is not proven to be non-prime.

Answer 4

An additional recommendation I can give is to improve the performance of the algorithm:

When searching for a prime number N the maximum iteration number (in this case variable i) shall be N/2. An example would be to test whether the number 7 is prime. It only makes sense to test whether the 7 is divisible by 2, 3 and 4. Any number that is greater than half of 7 will never be able to divide it without having a division remainder. In this case the numbers 5 and 6 will always give a division rest.

Another example, I want to know if 11 is cousin or not: I will test if 11 is divisible by 2, 3, 4, 5 and 6; Any number above that is not necessary to test, as it will always have division remainder greater than 1;