switches.c

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

#include "switches.h"

int main() {
    int num_switches_on;
    int *primes;
    int *switches;
    unsigned long int i, j;

    /* Initialize
     * -----------------------------------------------------------------------*/

    num_switches_on = MAX - 1;

    primes = (int *)malloc(sizeof(int) * MAX);
    switches = (int *)malloc(sizeof(int) * MAX);

    /* We'll the treat the arrays as one-indexed and use 2 as a dummy value */
    primes[0] = 2;
    switches[0] = 2;

    /* 1 is not prime */
    primes[1] = 0;

    /* The first switch is on. */
    switches[1] = 1;

    /* Prepare the arrays with default values. */
    for (i = 2; i < MAX; i++) {
        primes[i] = 1;
        switches[i] = 1;
    }

    /* Get prime numbers using the Sieve of Eratosthenes.
     * -----------------------------------------------------------------------*/

    /*
     * Loop through the primes array again and set each value whose position is
     * a multiple of another position to "0", i.e. mark the value as a composite
     * number
     */
    for (i = 2; i < MAX; i++)
        if (primes[i])
            for (j = i; i * j < MAX; j++)
                primes[i * j] = 0;


    /* Toggle the switches.
     * -----------------------------------------------------------------------*/

    for (i = 2; i < MAX; i++) {
        if (primes[i]) {
            toggle_switch(switches, i, &num_switches_on);

            /*
             * For successive switches with positions at prime numbers or with
             * positions at a multiple of a prime number, toggle that switch's
             * value.
             */
            for (j = i; i + j < MAX; j += i)
                toggle_switch(switches, i + j, &num_switches_on);
        }
    }

    /* Print array and number of switches.
     * -----------------------------------------------------------------------*/
    for (i = 0; i < MAX; i++)
        printf("%d ", switches[i]);

    printf("\n%d\n", num_switches_on);

    return 0;
}

/*
 * Change a switch's value from 0 to 1, indicating "off" to "on" and vice-versa.
 * Also, maintain the count of the number of switches in the on position.
 */
void toggle_switch(int *switches, int i, int *num_switches_on) {
    /* Store the value of the switch at "i" for further use. */
    int s = switches[i];

    if (s)
        (*num_switches_on)--;
    else
        (*num_switches_on)++;

    switches[i] = !s;
}

switches.h

#define MAX (100000000 + 1)

void toggle_switch(int *switches, int index, int *num_switches_on);