Przyspieszanie programu

Cześć,

mam program faktoryzację, który działa poprawnie. Przechodzi na sprawdzaczce testy ale na 85% i zalicza ale chciałbym aby działał na 100%.
Prawdopodobnie chodzi o przekroczenie limitu czasu.
Ktoś może powiedzieć jak przyspieszyć działanie programu?
Zadanie:
http://solve.edu.pl/contests/download_desc/2183
kod:
https://wandbox.org/permlink/KZzWY1MJY6byMwLn

1. Pętla zerująca tablicę sito zbędna skoro masz ją zdefiniowaną jako globalną, możesz wywalić.
2. podane zakresy mieszczą się w int, więc nie ma potrzeby używać long long
3. a zatem rozmiar tabeli możesz określić dynamicznie:

int *sito;

main()
{
    uint k;
    cin >> k;
   sito = new int[k]();//taki wydawałoby się cudaczny zapis załatwia od razu kwestię inicjalizacji komórki wartością 0
}

4. następnie ładujesz do każdej komórki tabeli liczbę do rozkładu na czynniki pierwsze

for (int cnt = 0; cnt < k; cnt++)
{
   cin >> sito[cnt];
}

a dalej to już robisz rozkład.

1. for (long long int i = 2; i * i < MAKS; i++) - w każdym obrocie pętli wyliczasz i**i (nie wiem jak tę gwiazdkę escapować :)) , możesz zastąpić przez warunek i< sqrt(MAKS), które obliczasz raz.
2. Możesz zmienić algorytm - teraz liczysz tę tablicę globalną dla 8M elementów, a na wejściu możesz mieć np. 5 liczb o wartości ...
   Może zamiast liczyć tę globalną tablicę, to weź się zastanów, czy nie lepiej dla każdej liczby rozważać dzielniki od 2..floor(sqrt(N))

Jak się nieco ruszy głową to okazuje się, że wielkie sito nie jest potrzebne.
A mniejsze sito da się je policzyć jako constexpr (w czasie kompilacji a nie w runtime)
https://wandbox.org/permlink/ODZ2TL4VgjJv6b0c

Ten kod będzie szybszy jeśli duża większość liczb testowych nie faktoryzuje się do liczb większych niż 2900.
Dlatego, może warto wpisać tam dużo większą wartość, na tyle ile pozwoli organicznie iteracji podczas liczenia constexpr.