Problem checking prime numbers

Question

I have to create a random number array in a range from 0 to 250, and show which are the primes. 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 taking the rest of the room, but I don’t know what it is.

Answer 1

Has two problems.

The first is inattention, 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;
    }

Makes more sense to you? Because the code runs like this. Note that the break is out of the if. In your code it seems that your intention was to put inside it. But as there is no key, only the first line of the else is a conditional line. The break always execute, be the if give true or false.

But none of this really matters 'cause there’s a bigger mistake.

The second problem is that logic is wrong. You have to go through all the divisions to make sure you’re cousin or not. After going through all (do all the for) you can compare and see if the number is prime. If all the loop is executed without leaving forcibly with break means that he has been able to test all divisions and no exact division has been given. 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]);
        }
    }
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

Answer 2

The reason the code doesn’t work is explained very well in the answer from @Maniero.

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

1. It is not necessary to divide the number being tested by multiples of 2, as no pair is prime other than the number 2.

2. Some mathematicians consider the number 1 as a cousin, but the accepted theory of factoring does not work that way, so most do not include the 1 on the list of cousins, 2 the first.

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

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 in Ideone

Answer 3

Let’s see your code, in the part where you test yourself n[i] is cousin:

        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 he tries to test if 6 is cousin:

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 number 5:

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

Now let’s check out number 2:

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

What’s going on?

He shows that he is cousin himself n[i]%j is different from zero (i.e., when it falls into the else). But that doesn’t mean n[i] is cousin, it just means j is not a divisor of n[i], and this will occur in the first face iteration with the 2 for all odd numbers greater than or equal to 3.

How to 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. ********

    }
}

Answer 4

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