What is going wrong with the logic?

Question

I'm trying to write a prime generator that implements the sieve of Eratosthenes. However, it includes some composite numbers (such as 25, 49 and other multiples of 5 and 7) in the output.

Here's my code:

/*****
 * To find out prime numbers from 1 to 100 with a different procedure
 * Author:Udit Gupta
 * Date:20/08/2011
 */

#include<stdio.h>

int main() {
    int a[100],i,j,k,n;

    for(i=0;i<=99;i++)
        a[i] = i+1;  /*1 to 100 numbers are entered into array*/

    /*Here te actual logic starts .......*/
    j = 1;
    while ( (a[j] != 0) && (j!=50) ) {
        k = 1;
        n = a[j];

        while( (n * k) < 99) {
            a[j+(n*k)] = 0;
            k++;
        }

        j++;
    }

    /*To print output of the array*/
    for (i=0;i<=99;i++) {
        if ( a[i] != 0)
            printf("\n%d",a[i]);
    }

    return 0;
}

Here is the output ....

    
udit@udit-Dabba ~/Desktop/letusc/ch8 $ gcc -o Dd Dd.c -Wall
udit@udit-Dabba ~/Desktop/letusc/ch8 $ ./Dd

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

Answer 1

1st hint: in a debugger, break on the n = a[j]; line. Run a few iterations. Does it ever stop when a[j] == 5?

udit@udit-Dabba ~/Desktop/letusc/ch8 $ gdb ./Dd
[GDB preamble elided]
(gdb) b main
Breakpoint 1 at 0x100000e63: file Dd.c, line 12.
(gdb) r
Starting program: /home/udit/Desktop/letusc/ch8/Dd
Reading symbols for shared libraries +. done

Breakpoint 1, main () at Dd.c:12
12      for(i=0;i<=99;i++)
(gdb) watch n
Hardware watchpoint 2: n
(gdb) c
Continuing.
Hardware watchpoint 2: n

Old value = 0
New value = 2
main () at Dd.c:21
21          while( (n * k) < 99) {
(gdb) c
Continuing.
Hardware watchpoint 2: n

Old value = 2
New value = 3
main () at Dd.c:21
21          while( (n * k) < 99) {
(gdb) p j
$1 = 2
(gdb) 

RMS's (no relation to that RMS) GDB tutorial includes a section on watchpoints, which the sample session above makes use of.

More hints to follow, as you need them.