I see lot of people mention precalculation but I have no idea how it works. I know they calculate some values and then they just use them but… that means the timer is started when they finish reading the input, how does that does not affect the resulting time of their answers? May someone explain me? Thanks in advance

Hello @cybuster

You have misunderstood what pre-calculation means. I shall try to explain with an example.

Question

Write a program to print the `n`

^{th} prime number for a given `n`

.

Input

First line of input contains a number `t`

. Then `t`

lines follow, each one containing an `n`

.

Output

For each of the test cases, output the `n`

^{th} prime number.

Constraints

1 <= t <= 5000

1 <= n <= 1000

Sample Input

6

3

5

1

3

2

4

Sample Output

5

11

2

5

3

7

Suppose you are writing a function `int nthPrime(int n)`

that returns the `n`

^{th} prime. That function will look something like this:

```
int nthPrime(int n)
{
int count = 0;
for (i = 2; ; ++i)
{
if (isPrime(i) == true)
{
++count;
}
if (count == n)
{
return i;
}
}
}
```

Now, from the constraints, it is obvious that a particular value of `n`

can repeat (`n`

can take only `1000`

values, but there can be `5000`

test cases, so some of the numbers must repeat). Imagine this worst case scenario input:

5000

1000

1000

.

. // 1000 is repeated 5000 times

.

1000

The answer for this test case will be

7919

7919

.

. // 7919 is repeated 5000 times

.

7919

Now, consider our function. For each test case, when we are passing the value of `n`

(which is `1000`

), it finds the `1000`

^{th} prime number (which is `7919`

). So, the for loop will run `7918`

times (loop starts at `2`

). Ignoring the time required for the `isPrime`

function used, we can conclude that the time takes is directly proportional to `7918`

. Let us call it `7918`

units (whatever this unit be). Now, this is repeated `5000`

times. So, total time taken will be around `5000 * 7918 (= 39590000)`

units.

Here, we are calculating the required values each and every time we need it.

Now consider another method of solving this problem – using pre-calculation.

We will have a function `init`

, that will calculate all `1000`

primes and store it in an array. Then, the function `nthPrime`

simply returns the number from the corresponding index in that array.

It looks something like this:

```
int primes[1000];
void init()
{
int count = 0;
for (i = 2; ; ++i)
{
if (isPrime(i) == true)
{
primes[count] = i;
++count;
}
}
}
int nthPrime(int n)
{
return primes[n - 1];
}
```

Here, we call the init function even before we start taking inputs. So, the `init`

function takes about `7918`

units of time. Now, our `nthPrime`

function will take only `1`

unit of time. So, total time taken for `5000`

test cases will be around `7918 + 5000 (= 12918)`

units. This one is about `39590000 / 12918 (~ 3000)`

times faster than the previous solution. In fact, considering the complexity of the `isPrime`

function as well, the total speed up obtained using precalculated values is very much than computing values as and when required.

Now, the timer starts not just before starting to take input. Timer starts at the very beginning of the execution of your program. So everything you are doing in your program will add to the execution time of your program. Precalculation is usually used when you will be needing to calculate some fairly easily calculable values a lot of times.