Conquering Project Euler #7: Finding the 10001st Prime in C

Now that we’ve got a solid grasp on prime numbers, let’s get started with the C code!

The C Code

#include <stdio.h>
#include <stdbool.h>

bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int count = 0;
    int num = 2;
    while (count < 10001) {
        if (isPrime(num)) {
            count++;
            if (count == 10001) {
                printf("The 10001st prime number is: %d\n", num);
                break;
            }
        }
        num++;
    }
    return 0;
}

Breaking Down the Code

Let’s dissect the code step by step to understand what’s happening behind the scenes.

• #include <stdio.h> and #include <stdbool.h>: We’re including the necessary header files for input/output and boolean operations.
• bool isPrime(int num): This function takes an integer as input and returns a boolean value indicating whether the number is prime or not.
• if (num <= 1) return false;: We’re checking if the input number is less than or equal to 1, in which case it’s not prime.
• for (int i = 2; i * i <= num; i++): This loop checks for divisibility from 2 to the square root of the input number. Why the square root, you ask? Because a larger factor of the number would be a multiple of a smaller factor that has already been checked!
• if (num % i == 0) return false;: If the input number is divisible by any of the checked numbers, it’s not prime.
• return true;: If the number passes all the checks, it’s prime!
• int main(): Our main function is where the magic happens.
• int count = 0; and int num = 2;: We’re initializing a counter to keep track of prime numbers and starting from 2, the first prime number.
• while (count < 10001): This loop will continue until we’ve found the 10001st prime number.
• if (isPrime(num)): We’re calling our isPrime function to check if the current number is prime.
• count++; and if (count == 10001): If the number is prime, we increment the counter and check if we’ve reached our target of 10001 primes.
• printf("The 10001st prime number is: %d\n", num);: When we finally find the 10001st prime, we print it to the console and exit the loop.

Optimizations and Variations

While the above code gets the job done, there are some optimizations and variations we can explore to make our code more efficient and robust.

Sieve of Eratosthenes

One of the most popular methods for finding prime numbers is the Sieve of Eratosthenes. This algorithm works by iteratively marking the multiples of each prime number starting from 2. The remaining unmarked numbers in the list are primes.

void sieveOfEratosthenes(int limit) {
    bool isPrime[limit + 1];
    for (int i = 0; i <= limit; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; count < 10001; i++) {
        if (isPrime[i]) {
            count++;
            if (count == 10001) {
                printf("The 10001st prime number is: %d\n", i);
                break;
            }
        }
    }
}

Memory Optimization

In our original code, we’re using a boolean array to store the primality of each number. However, we can optimize this by using a bit array, which reduces the memory usage significantly.

#define BITS_PER_BYTE 8
#define BYTE_TO_BINARY(byte) \
    (byte && 0x80 ? '1' : '0'), \
    (byte && 0x40 ? '1' : '0'), \
    (byte && 0x20 ? '1' : '0'), \
    (byte && 0x10 ? '1' : '0'), \
    (byte && 0x08 ? '1' : '0'), \
    (byte && 0x04 ? '1' : '0'), \
    (byte && 0x02 ? '1' : '0'), \
    (byte && 0x01 ? '1' : '0')

void printBinary(byte byte) {
    printf("%c%c%c%c%c%c%c%c ", BYTE_TO_BINARY(byte));
}

int main() {
    int limit = 1000000; // approximately 7845 primes
    byte sieve[limit / BITS_PER_BYTE + 1];
    for (int i = 0; i < (limit / BITS_PER_BYTE + 1); i++) sieve[i] = 0xFF;
    sieve[0] = 0x7F; // 01111111
    for (int i = 2; i * i <= limit; i++) {
        if (!(sieve[i / BITS_PER_BYTE] & (1 << (i % BITS_PER_BYTE)))) {
            for (int j = i * i; j <= limit; j += i) {
                sieve[j / BITS_PER_BYTE] &= ~(1 << (j % BITS_PER_BYTE));
            }
        }
    }
    int count = 0;
    for (int i = 2; count < 10001; i++) {
        if (!(sieve[i / BITS_PER_BYTE] & (1 << (i % BITS_PER_BYTE)))) {
            count++;
            if (count == 10001) {
                printf("The 10001st prime number is: %d\n", i);
                break;
            }
        }
    }
    return 0;
}

Conclusion

Congratulations! You’ve successfully conquered Project Euler’s 7th problem and found the 10001st prime number in C. Remember, the key to solving this problem lies in understanding prime numbers and using efficient algorithms to find them.

Whether you opted for the original code, the Sieve of Eratosthenes, or memory optimization, the most important takeaway is the journey itself. You’ve improved your coding skills, learned new techniques, and experienced the thrill of problem-solving.

So, what’s next? Take on more challenges, explore new programming languages, and never stop learning. The world of coding is full of endless possibilities

Frequently Asked Question

Get ready to dive into the world of prime numbers and coding!