Problem in checking prime numbers

6

I have to create a vector of random numbers in a range of 0 to 250, and show which cousins are. This is my code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
    int i,j,n[10];

    srand(time(NULL));
    for(i=0 ; i < 10 ; i++) {
        n[i]=rand()%250;
        printf("%d numero: %d\n",i,n[i]);
    }
    printf("\n");
    for (i=0; i<10; i++) {
        for (j=2; j<n[i]; j++) {
            if (n[i]%j==0) {}
            else
                printf("O numero %d e primo\n",n[i]);
                break;
        }
    }
}

I'm pretty sure there's something wrong with getting the rest of the division, but I do not know what it is.

    
asked by user20153 19.12.2014 в 01:01

4 answers

4

You have two problems.

The first is inattentiveness, very common among programmers who do not get used to using keys to define block always. See this code:

    for (j=2; j<n[i]; j++) {
        if (n[i]%j==0) {
        } else {
            printf("O numero %d e primo\n",n[i]);
        }
        break;
    }

Does it make more sense to you? Because the code performs like this. Note that break is outside if . In your code it seems that your intention was to put inside it. But since it has no key, only the first line of else is a conditional line. The break always executes, whether the if is true or false.

But none of this matters much because it has a bigger error.

The second problem is that the logic is wrong. You have to go through all the divisions to make sure you are prime or not. After going through all of them (doing all for ) you can compare and see if the number is prime. If all the loop runs without exiting with break means that it has been able to test all divisions and none has given exact division. This is the definition of what is prime or not.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    int i, j, n[10];

    srand(time(NULL));
    for(i = 0; i < 10; i++) {
        n[i] = rand() % 250;
        printf("%d numero: %d\n", i, n[i]);
    }
    printf("\n");
    for (i = 0; i < 10; i++) {
        for (j = 2; j < n[i]; j++) {
            if (n[i] % j == 0) { //deu divisão exata então já sabemos que não é primo
                break; //se não é primo pode parar de verificar cada divisão
            }
        }
        if (n[i] == j) { //verifica se o loop executou por completo, aí é primo
            printf("O numero %d e primo\n", n[i]);
        }
    }
}

See running on ideone . And no Coding Ground . Also I put it in GitHub for future reference .

    
19.12.2014 в 01:28
3

The reason the code does not work is explained very well in the @Maniero response.

However, there are some additional details that can be improved:

  • It is not necessary to divide the number being tested by multiples of 2, since no pair is prime beyond number 2.

  • Some mathematicians consider the number 1 as prime, but the accepted theory of factorization does not work that way, so most do not include 1 in the list of primes, with 2 being the first.

    I set the code to work this way and print the result also for numbers that are not prime.

    int main(void) {
        int i, j, n[10];
    
        srand(time(NULL));
        for(i = 0; i < 10; i++) {
            n[i] = rand()%250;
            printf("%d numero: %d\n", i, n[i]);
        }
        printf("\n");
        for (i = 0; i < 10; i++) {
            if (n[i] <= 1) {
                printf("O numero %d nao e primo\n", n[i]);
            } else if (n[i] == 2 || n[i] % 2 != 0) {
                for (j = 3; j < n[i]; j++) {
                    if (n[i] % j == 0) {
                        printf("O numero %d e divisivel por %d\n", n[i], j);
                        break;
                    }
                }
                if (n[i] <= j) {
                    printf("O numero %d e primo\n", n[i]);
                }
            } else {
                printf("O numero %d e divisivel por %d\n", n[i], 2);
            }
        }
    }
    

    Code on IdeOne

        
    19.12.2014 в 15:37
    1

    Let's look at your code, where you test whether n[i] is prime:

            for (j=2; j<n[i]; j++) {
                if (n[i]%j==0) {}
                else
                    printf("O numero %d e primo\n",n[i]);
                    break;
            }
    

    Let's see what happens when it tries to test if 6 is prime:

    n[i] = 6, j = 2, 6 % 2 == 0, nada acontece
    n[i] = 6, j = 3, 6 % 3 == 0, nada acontece
    n[i] = 6, j = 4, 6 % 4 == 2, imprime "O numero 6 eh primo", break
    

    Now let's do the same with the number 5:

    n[i] = 5, j = 2, 5 % 2 == 1, imprime "O numero 5 eh primo", break
    

    Now let's check the number 2:

    Não entra no laço, não imprime nada.
    

    What's happening?

    It shows that it is prime if n[i]%j is non-zero (that is, when it falls in else ). But that does not mean that n[i] is prime, it means only that j is not a divisor of n[i] , and this will occur in the first iteration of face with 2 for all odd numbers greater than or equal to 3.

    How do I fix this?

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int main(void)
    {
        int i,j,n[10];
    
        srand(time(NULL));
        for(i=0 ; i < 10 ; i++) {
            n[i]=rand()%250;
            printf("%d numero: %d\n",i,n[i]);
        }
        printf("\n");
        for (i=0; i<10; i++) {
    
            // ******** Início do trecho corrigido. ********
            int primo = 1; // Ou seja, é primo até provar o contrário.
            for (j=2; j<n[i]; j++) {
                if (n[i]%j==0) {
                    // j é um divisor de n[i], então não é primo.
                    primo = 0;
                    break;
                }
            }
            // Se terminou o laço sem achar nenhum divisor, então é primo
            if (primo) printf("O numero %d e primo\n",n[i]);
            // ******** Fim do trecho corrigido. ********
    
        }
    }
    
        
    19.12.2014 в 01:31
    0

    Up to 250 makes a table ...

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int diff(const void *, const void *);
    
    static int primo[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
          53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
          131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
          199, 211, 223, 227, 229, 233, 239, 241};
    
    int main(void) {
        srand(time(0));
        for (int numeroaleatorio = 250; numeroaleatorio > -1; numeroaleatorio--) {
            int *r = bsearch(&numeroaleatorio, primo,
                  sizeof primo / sizeof *primo, sizeof *primo, diff);
            if (r) printf("%d 'e numero primo\n", numeroaleatorio);
            if (!numeroaleatorio) break;
        }
        return 0;
    }
    
    int diff(const void *a, const void *b) {
        const int *aa = a;
        const int *bb = b;
        return *aa - *bb;
    }
    
        
    19.11.2015 в 17:15