Problem to find prime numbers

Question

Problem to find prime numbers

Navigation

#1 by (6 votes)
#2 by (3 votes)
#3 by (3 votes)
#4 by (0 votes)

5

Today in college I learned about for and while . However, the code I am trying to formulate does not spin. It compiles but "buga" after it puts the value. The code is simply for verification 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");
}

c

asked by anonymous 24.03.2014 / 21:53

4 answers

Using JSP and JAVA Hide the keyboard

score 6 · 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);

By 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 mgibsonbr notes, using break would be interesting to keep checking inside the main function:

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

score 3 · Answer 2

Let's see what happens to 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

score 3 · Answer 3

Your problem, as the other answers pointed out, is that you are subtracting 1 from i and then by doing an operation involving i - 1 . The most straightforward way to resolve this is to move the decrement from i to 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 in 2 instead of 1 , otherwise you will eventually a % 1 which is always 0 (i.e., the program will say that every number is "No cousin").

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

With each 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");

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

Otherwise, there is the use of break - which you may not have learned yet. Spoiler: It serves to stop an early loop. If inside if you put an additional statement - break; - so now that he knows for sure that the number is not prime he does not have to continue testing, he stops right there. There is also a way to stop earlier without using break :

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

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

score 0 · 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 number of the iteration (in this case the variable i) should be N / 2. An example would be to test if the number 7 is prime. It only makes sense to test whether 7 is divisible by 2, 3, and 4. Any number that is greater than half of 7 could never divide it without having a remainder of division. In this case the numbers 5 and 6 will always give a remainder of division.

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