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

int* sieveOfEratosthenes(int n) {
    bool *isPrime = (bool *)malloc((n + 1) * sizeof(bool));

    for (int i = 0; i <= n; i++) {
        isPrime[i] = true; // Initialize all numbers as prime
    }

    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime numbers

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p] == true) {
            // Mark multiples of p as not prime
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i] == true) {
            count++; // Count the number of primes
        }
    }

    int *primes = (int *)malloc((count + 1) * sizeof(int)); // Allocate space for prime numbers

    int index = 0;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i] == true) {
            primes[index++] = i; // Store prime numbers in the array
            printf("%d ", i);
        }
    }

    primes[index] = 0; // Set the end of the array with 0 as a terminator

    free(isPrime);
    return primes;
}


int* sieveOfEratosthenes2(int n) {
    //malloc
    int *primes = (int *)malloc((n + 1) * sizeof(int));

    for (int i = 0; i <= n; i++) {
        if(i%2==0) primes[i] = 0;    // Obvously, odd numbers (except 2) are not primes
        else primes[i] = 1;          // Initially, consider all even numbers as prime
    }

    /*
    //calloc (initializes the allocated memory block to zeros)
    int *primes = (int *)calloc((n + 1), sizeof(int));

    for (int i = 4; i <= n; i += 2) {
        primes[i] = 0; // All even numbers greater than 2 are not prime
    }

    // or make array statically
    int size = ((n + 1) / 2); // Determine size for odd numbers only
    int primes[size];
    */

    primes[0] = primes[1] = 0; // 0 and 1 are not prime numbers
    primes[2] = 1;            // 2 is a prime number

    //main part of the algotirhm
    for (int p = 3; p * p <= n; p++) {
        if (primes[p] == 1) {        //do not check already cross out
            // Setting of the multiples of p from p^2 as not-primes (0)
            for (int i = p * p; i <= n; i += (p * 2)) {     //i=i+(p*2) is for considering only odd multiples of p
                primes[i] = 0;       //this is multiple of p, thus it is not prime
                //printf("%d %d %d\n", p, i, n);
            }
        //printf("\n");
        }
    }

    return primes;
}

int main() {
    int limit; // Change this limit to find primes up to a different number
    printf("Enter the limit to find prime numbers: ");
    scanf("%d", &limit);

    printf("\nPrime numbers up to %d are:\n", limit);

    FILE *file = fopen("/tmp/prime_numbers.txt", "w");
    if (file == NULL) {
        printf("Error creating file!\n");
        return 1;
    }

    //version 1 (bool)

    int *primes = sieveOfEratosthenes(limit);
    for (int i = 0; primes[i] != 0; i++) {
        printf("%d ", primes[i]); // Print prime numbers
        fprintf(file, "%d ", primes[i]);
    }

    /*
    //version 2 (some optimizations added)
    int *primes = sieveOfEratosthenes2(limit);
    for (int i = 0; i <= limit; i++) {
        if (primes[i] == 1) {
            printf("%d ", i); // Print prime numbers
            fprintf(file, "%d ", i);
        }
    }
    */
    fclose(file);
    free(primes); // Free the memory allocated for primes
    return 0;
}