Weird Output in for loop in C (Repetitive numbers)

Question

This is my code for finding prime numbers.

int main (void){
    int p, d;
    _Bool isprime;

    for (p=2;p<=50;++p){
        isprime = 1;

        for (d=2;d<p;++d){
            if (p%d == 0)
                isprime = 0;

            if (isprime != 0)
                printf("%i ", p);
        }
    }

    return 0;    
}

The output of this program is

3 5 5 5 7 7 7 7 7 9 11 11 11 11 11 11 11 11 11 13 13 13 13 13 13 13 13 13 13 13 15 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 21 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 25 25 25 27 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 33 35 35 35 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 39 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 43 45 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 49 49 49 49 49

The numbers seem to be right, but they are repetitive. Is there something wrong with my code? Or is there something wrong with the compiler? Every time I use a for loop (not just this program) the output is like this. How do I fix this?

Thanks in advance!(Sorry for my bad English)

Answer 1

You have to use break statement. Without break, every time the calculation is performed, thus so many repetition in your original code. But even with break statement your code will generate many non desirable numbers/output instead of just generating prime numbers. So i have written following code for you. It will generate prime numbers as per your question. Use the following code for generating prime numbers upto 50.

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


int main ()
{

    int prime,i,k,j,max;
    printf("2\n");
    printf("3");

    for(i=4; i<max; i++)
    {
        if(i%2!=0 && i%3!=0 && i%5!=0 && i%7!=0)
        {
            prime=i;
            printf("\n%d",prime);
            k++;
        }
    }
}

Answer 2

You need to put your printf lines outside your inner loop.

Like this:

int main (void)
{
    int p, d;
    _Bool isprime;
    for (p=2;p<=50;++p){
        isprime = 1;
        for (d=2;d<p;++d){
            if (p%d == 0) {
                isprime = 0;
                break;
            }
        }
        if (isprime)
            printf("%i ", p);
    }
    return 0;
}

Answer 3

Others have given tips. Some of them are useful, some of them are not. The end goal is to print all prime numbers only. So checking if the number 6 is prime, we start with d = 2. So we check 6 % 2. Well that is equal to 0. We know that 6 is NOT prime. We should move on to 7. Instead we have incremented 2 to 3 and now we check again. 6 % 3... we do this for every number less than the number we are trying to check. This greatly adds to the computational complexity. This program runs very close to BigTheta(n^2). An easier way to run this would be a do-while loop or through the use of a break statement. Since you're using C, use an int as a bool marker (to prevent another lib import). Your inner loop would look like this:

    int is_prime = 1;
    for (d = 2; d < p; d++)
    {   
       if (p % d == 0)
       {
          is_prime = 0
          break;
       }
    }
    if (is_prime)
       printf("%d ", p);

There are additional methods of reducing the complexity, but those rely on better algorithm design moreso than more efficient code. For a beginner's project, think about why the current version of your code is inefficient (even if it was working properly). A lot of it comes with experience, but you shouldn't neglect individual code- and algorithm review.

Answer 4

The problem with your code, is that it prints p multiple times, for the same value of p. Like Eugene Sh. stated in a comment, it's easily fixed by moving the if statement up a level, to the outer for loop. I also changed is_prime to a bool value, and edited how it's set.

int max_p = 50;
int p, d;
bool is_prime;

for (p = 2; p <= max_p; ++p) {
    is_prime = true;

    for (d = 2; d < p; ++d) {
        if (p % d == 0) {
            is_prime = false;
            break;
        }
    }

    if (is_prime) {
        printf("%i ", p);
    }
}

I will assume that I used C++ doesn't make a difference.