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

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

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;

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;

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;

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