Primorial

解説

Lucy DPをすることを考えます。$f(n,x)$を$x$以下の素数で篩って残った正の整数の積とします。求めるものは$f(n,\sqrt n)$です。また、$g(n,x)$を$x$以下の素数で篩って残った正の整数の個数とします。
この時、以下の漸化式が成り立ちます。

$$\begin{equation*} f(n,x)= \begin{cases} n! & \text{if $x=1$}\\ \frac{f(n,x-1)f(x-1,x-1)}{f(\lfloor\frac{n}{x}\rfloor,x-1)x^{g(\lfloor\frac{n}{x}\rfloor,x-1)-g(x-1,x-1)}} & \text{if $x^2\le n$, $x$ is prime}\\ f(n,x-1) & \text{otherwise} \end{cases} \end{equation*}$$

$$\begin{equation*} g(n,x)= \begin{cases} n-1 & \text{if x=1}\\ g(n,x-1)-g(\lfloor\frac{n}{x}\rfloor,x-1)+g(x-1,x-1) & \text{if $x^2\le n$, $x$ is prime}\\ g(n,x-1) & \text{otherwise} \end{cases} \end{equation*}$$

初期値の$n!$を$998244353$で割った余りは高速に計算できることが知られています。Library Checker
また、(高速な)エラトステネスの篩や埋め込みなどでも解けます。