Thread: Trying to learn C on my own

Hey,

So I'm trying to learn C on my own, and I've just started through a book and am having a problem with an exercise.

Problem: There are 500 light bulbs (numbered 1 to 500) arranged in a row. Initially they are all OFF.

Starting with bulb 2, all even numbered bulbs are turned ON. Next, starting with bulb 3, and visiting every 3rd bulb, it is turned ON if it is OFF, and it is turned OFF if it is ON.

This procedure is repeated for every fourth bulb, then every fifth bulb, and so on up to the 500th bulb. Write a program to determine which bulbs are OFF at the end of the exercise.

The result I'm getting with the code below is that only the first bulb is OFF at the end, which I don't believe can possibly be correct becuase the prime numbered bulbs should never be changed from OFF.

Any help on where I made a mistake?

Thanks

Code:

 
#include <stdio.h>

int main()
{
    int numbulbs = 501, i = 0, j = 0, k = 0;
    int bulbs[numbulbs];
    
    for(i = 0; i <= numbulbs; i++)
    {
        bulbs[i] = 0;            // all bulbs set to OFF
    }
    
    for (j = 2; j <= numbulbs; j++)
    {
        for (k = j; k<=numbulbs; k++)
        {
            if( ( k%j ) == 0)
            {
                if(bulbs[k] == 1)
                    bulbs[k] = 0;
                if(bulbs[k] == 0)
                    bulbs[k] = 1;
            }        
        }
    }
    
    for( j = 1; j <= numbulbs; j++)
    {
        if (bulbs[j] == 0)
            printf("Bulb number %i is OFF\n", j);
    }
    return 0;
}

Hold on!

Next, starting with bulb 3, and visiting every 3rd bulb, it is turned ON if it is OFF, and it is turned OFF if it is ON.

Isn't the 3rd bulb a prime number bulb? Doesn't it get turned ON?

Here's a way to look at this - set out say, 10 pennies on the table, and say heads side is the ON state, and tails side is OFF. Now go through your exercise with switching - what is the result?

It would be no different for 500 items.

Ok, so going through it that way the bulbs that are off are #1, #4, #9 so it seems as if the the squares of the integers will be the ones that are off in the end. So I could change to program to use that result rather easily.

But assuming I didn't know that result, there must be a flaw in the original program that I'm just not seeing, or my thinking itself is flawed. Since this is only the 2nd chapter of the book and I haven't written a ton of programs I really want to get the logic and looping down well.

I'm not sure why you conclude prime numbers would never be changed. 2, 3, 5... these are prime numbers and it's clear to see that they are turned on. And since you are traversing the whole array with your j index, 1 step at a time, you are clearly starting your inner loop at each successive number. What's interesting is that all your prime multiples are turned off in the end.

You do have a logic problem to sort first though. Arrays of size N are indexed from 0 to N-1, not 1 to N. So, when j = numbulbs = 501, your loops execute and operate on bulbs[501] which is out of bounds of the array - treading on something else's memory.

Generally you do

Code:

for( initialize  ;  index < SIZE ; increment index )

I suppose indexing from 2 onward is OK if it is more logical to you, then you don't need to change your loop tests, or the if( k%j ) test, but you'll have to adjust your bulbs indexing. IE. when j=k=2, bulbs[2] is 3rd element, not 2nd. Either way, you need to adjust your first loop that initializes to zero, and your last loop for printing.

Now, your main logic problem is that first you turn bulbs[k] to zero if 1, but then you change it back to 1! Use if/else-if.

Ah! Stupid mistake! I just changed that to an else if and everything was fine. What I with the indexing was just to have the bulb number correspond to the same index number. So I have a bulb at index 0, but I never touch it and just pretend it isn't there. I know the indexing of the array itself goes from 0 to n-1, I'm just following this particular book as the problem said it wanted the bulbs numbered 1 to 500.

The prime thing bad thinking on my part, just trying to come up with something.

Thanks a lot!

OK, but still when i = j = k = 501, the loops execute and bulbs[k] is out of bounds;

That's a good point that I didn't notice before you pointed it out as well. It seemed gcc usually gave me an error or warning for that type of mistake before, so I'll have to pay more attention to my arrays. I only got the warning for not using a #define for the array length, but I didn't because I though I'd just follow closely along with the book.

Thanks for all the help!