Solving C Programming Problem: Finding Primes to 1000

[kbaumen]

I do encounter a lot of problems while learning C. For example the code below, I can't understand why doesn't it work. It's meant to print out all primes to 1000 by using the sieve method. However, I only get a blank line. And I've spent about two hours making small modifications and repeatedly rereading the code with no result. Can anyone tell me why doesn't it work?

Here's the code:

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

#define PRIME 1
#define NONPRIME 0

int numbers[1000];

void mark_multiples(int num)
{
    int a, j;  
    a = 0;
    j = 2;  

    while (a < 1000)
    {
        a = num * j;

        if (a >= 1000)
        {
            break;
        }

        numbers[a] = NONPRIME;
        j++;
    }
}

int get_next_prime(int num)
{
    int answer;

    answer = num + 1;

    while (numbers[answer] == NONPRIME)
    {
        answer++;
        if (answer == 1000)
        {
            break;
        }
    }

    return answer;
}

int main(void)
{
    int i, next_prime;
    
    numbers[0] = NONPRIME;
    numbers[1] = NONPRIME;

    for (i = 2; i < 1000; i++)
    {
        numbers[i] = PRIME;
    }

    next_prime = 2;    
    
    do
    {
        mark_multiples(next_prime);
        next_prime = get_next_prime(next_prime);
    }
    while(next_prime < 1000);

    for (i = 1; i < 1000; i++);
    {

        if (numbers[i - 1] == PRIME)
        {
            printf("%i ", i);
        }
    }
    
    printf("\n");

    return 0;
}

Thank you in advance.

 

[jtbell]

Have you tried putting extra printf statements at key points in the code, to see what is actually happening to your variables? That often gives you clues as to what's wrong, faster than by just staring at the code. When doing this, it would probably help to reduce the upper limit temporarily from 1000 to perhaps 30, so the resulting output doesn't overwhelm you.

I haven't looked at your code in detail myself... I'm just offering a general suggestion.

 

[kbaumen]

Well, thanks for the suggestions. I tried reducing the 1000 to 100. But that idea of more printf's sounds quite good

...

That worked. I changed the last loop from FOR to WHILE like this:

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

#define PRIME 1
#define NONPRIME 0

int numbers[1000];

void mark_multiples(int num)
{
    int a, j;  
    a = 0;
    j = 2;  

    while (a < 1000)
    {
        a = num * j;

        if (a >= 1000)
        {
            break;
        }

        numbers[a] = NONPRIME;
        j++;
    }
}

int get_next_prime(int num)
{
    int answer;

    answer = num + 1;

    while (numbers[answer] == NONPRIME)
    {
        answer++;
        if (answer == 1000)
        {
            break;
        }
    }
    return answer;
}

int main(void)
{
    int i, next_prime;
    
    numbers[0] = NONPRIME;
    numbers[1] = NONPRIME;

    for (i = 2; i < 1000; i++)
    {
        numbers[i] = PRIME;
    }

    next_prime = 2;    
    
    do
    {
        mark_multiples(next_prime);
        next_prime = get_next_prime(next_prime);
    }
    while(next_prime < 1000);

    i = 0;
    
    while (i < 1000)
    {
        if (numbers[i] == PRIME)
        {
            printf("%i  ", i);
        }
        
        i++;
    }
    
    printf("\n");

    return 0;
}

Now it works perfectly. Thanks for the help.

However, I still have no idea why the previous one didn't work. All I changed is FOR to WHILE in main routine.

 

[t!m]

You have a semi-colon after the for statement.

 

[kbaumen]

You have a semi-colon after the for statement.

Thanks. That really was the problem. Got to be more careful.

 

[Texpie]

gdb?

 

[kbaumen]

gdb?

I'm sorry, what do you mean by that? What's gdb?

 

[Rogerio]

I'm sorry, what do you mean by that? What's gdb?

GDB stands for GNU Debugger.

But I think it is not a good sugestion: before using any debugger, you should be able to correct a piece of code like this by yourself - alone.