/*
 * Copyright 2026 betterip (https://betterip.org)
 *
 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

// made with <3 in vim

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>

#define CLRBIT(input, position) ((input) &~(1 << (position))) // sets a single bit at specified position to 0
#define GETBIT(input, position) ((input) & (1 << (position))) // gets a single bit at specified position

/*
 * idk just check the last number tends to lie on that one
 * TODO:
 * fix the problem above
 * make the code faster and more efficient
 */

// i << 3 and i * 8 is equivalent

int main() {
	// Making a GIGANTIC output buffer, so it's fast
        size_t buffer_size = (size_t)1 << 24;
        char *output_buffer = malloc(buffer_size);

        if (output_buffer == NULL) {
                printf("Output buffer inicialization failed!\n");
                return 1;
        }

        setvbuf(stdout, output_buffer, _IOFBF, buffer_size);

        uint64_t max;
        printf("Enter the number up to which primes should be computed: ");
        fflush(stdout);
        scanf("%" SCNu64, &max);

        max -= 2;
        max = ((max >> 4) + 1) << 4;	// makes it a multiple of 16
        uint64_t bytes = max >> 4;	// divides by 16 to allocate the appropriate amount of memory

	// Allocate memory dynamically for the array
        uint8_t* working_list = (uint8_t*)malloc(bytes);
        if (working_list == NULL) {
                printf("Memory allocation failed!\n");
                return 1;
        }

	// Initialize the array
	memset(working_list, 255, bytes);

        uint64_t lim = (uint64_t)(sqrt(max) / 16 + 1);						// limits the searched bytes to those containing numbers that fall roughly under the sqrt of the biggest number

        for (uint64_t i = 0; i < lim; i++) {
                for (uint8_t j = 0; j < 8; j++) {						// uint8_t is guaranteed to be 8 bits long, though 3 would be sufficient in this case
                        if (GETBIT(working_list[i], j)) {					// if still a prime
                                uint64_t step = (i << 4) + (j << 1) + 3;			// step size
                                uint64_t offset = step * step;					// initialize offset equal to step^2
                                step = step << 1;						// to rule out multiplying by even numbers

                                while (1) {
                                        uint64_t pos    = (offset - 3) >> 4;			// the byte's index
                                        uint8_t  pos_16 = (offset - 3 - (pos << 4)) >> 1;	// position within the byte

                                        working_list[pos] = CLRBIT(working_list[pos], pos_16);

                                        offset += step;
                                        if (offset > max) {
                                                break;
                                        }
                                }
                        }
                }
        }

	// Print the prime numbers
        printf("2\n");
        for (uint64_t i = 0; i < bytes; i++) {
                for (uint8_t j = 0; j < 8; j++) {
                        if (GETBIT(working_list[i], j)) {
                                printf("%" PRIu64 "\n", (uint64_t)((i << 4) + (j << 1) + 3));
                        }
                }
        }

	// in case anything's left over in the printing buffer
        fflush(stdout);

	// Free all the dynamically allocated memory
        free(working_list);
        free(output_buffer);

        return 0;
}