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.

Answer 2

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

This code is dangerous. You may well end up with j + n * k being larger than 99, which will overwrite arbitrary memory (or, strictly speaking, the behavior is undefined). Better be safe:

#include <assert.h>

...

while (n * k < 99) {
  int index = j + n * k;
  assert(0 <= index && index < 100);
  a[index] = 0;
  k++;
}

Answer 3

Honestly, do yourself a favor and do a web search on "tutorial on gdb debugger". You'll get hundreds of hits. Then, sit down and have some fun learning a powerful tool that you will spend hundreds and hundreds of hours using if you continue to learn C, C++, or a dozen other computer languages. (I'm serious about the 'fun' part; I you don't find it fun, drop CS!)

Also do a search on 'ddd debugger'; this is a free OSS graphical front-end to gdb -- very nice, IMHO.

-k

Answer 4

hint ; look at what happened to 5 and hence 25

google will tell you how to use gdb - its not hard

a[j + n * k] = 0;

I think you mean

a[n * k] = 0;

Answer 5

You are storing your results (marking non-primes as zero) in the same array as you are reading from within the outer loop.

The number 4 gets (correctly) marked as non-prime, but this has the unwanted side-effect of terminiating your main loop (because a[j] ==0).

So you only process n=2 and n=3.

Answer 6

The problem is that the loop ends far too soon. if a == 3, a[j] == 0 and the loop ends. Change your main loop to:

for (j = 1; j < 50; j++) 
{
    k = 1;
    n = a[j];

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