เฉลยข้อ Prime ตัวที่ n การแข่งขัน TOI10

TOI10-Prime.c

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

int main()
{
    unsigned int *primes;
    unsigned int primesCount=1, primesLimit=16;

    unsigned int primeNeeded;

    unsigned int currNumber, currPrime;
    double currNumberSqrt;
    int isPrime;

    primes = malloc(primesLimit * sizeof(unsigned int));
    primes[0] = 2;

    scanf("%u", &primeNeeded);

    currNumber = 3;
    while (primesCount < primeNeeded) {
        currNumberSqrt = sqrt(currNumber);
        currPrime = 0;
        isPrime = 1;

        while (primes[currPrime] <= currNumberSqrt) {
            if (currNumber % primes[currPrime] == 0) {
                isPrime = 0;
                break;
            }
            currPrime++;
        }

        if (isPrime) {
            if (primesCount == primesLimit) {
                primesLimit *= 2;
                primes = realloc(primes, primesLimit * sizeof(unsigned int));
            }

            primes[primesCount] = currNumber;
            primesCount++;
        }

        currNumber += 2;
    }

    printf("%u\n", primes[primeNeeded-1]);

    return 0;
}