A composite number is always at least as big as the square of its least prime factor. So if a number is composite, it will have a factor no larger than its square root, as you have shown.
Examples like $289=17 \times 17$ show that you can't do better than this. With different prime factors you can take something like $29\times 31 = 899$ and you can't do better.
The second example - which is not a prime power - depends on primes being close together - although the twin prime conjecture (infinitely many pairs of primes with difference $2$) is still open, there are now known to be infinitely many pairs of primes with small differences.
The claim you quote, that checking three digit numbers to see if they are prime powers is difficult is frankly ludicrous. I can do that fairly efficiently in my head. There are not many prime squares, and beyond that the powers of $2,3,5,7$ are not difficult to identify.
Q1.
We have the primes
$$p_1<p_2<\ldots <p_n $$
and want to pick $x$ such that $x^2\bmod p_i$ differes for all $i$.
For odd $p$, there are $\frac{p+1}2$ quadratic remainders modulo $p$, and we always have $\frac{p_i+1}2>i-1$. Therefore, it is always possible to pick a quadratic remainder modulo $p_i$ that differs from any quadratice remainders modulo $p_j$, $j<i$, picked before. Therefore, it is possible to pick $a_1,\ldots, a_n$ such that $a_i^2\bmod p_i\ne a_j^2\bmod p_j$ for $i\ne j$. The Chinese Remainder Theorem guarantees that there exists $x$ with $0\le x< p_1p_2\cdots p_n-1$ such that $x\equiv a_i\pmod {p_i}$ for all $i$, and hence $x^2\bmod p_i$ determines $i$ uniquely, as desired.
Unfortunately, $p_1p_2\cdots p_n$ is an undesirably large bound.
We may ask: How many numbers $x\in\{0,\ldots, p_1\cdots p_n-1\}$ can solve the problem? We can pick $x\bmod p_1$ arbitrarily in $p_1$ ways. This excludes at most two choices of $x\bmod p_2$, so here we still have $p_2-2$ choices. For $x\bmod p_3$, at most four choices are "forbidden", hence we still have $p_3-4$ choices. And so on. We conclude that there are at least
$$p_1(p_2-2)(p_3-4)(p_4-6)\cdots (p_n-2n+2) $$
good choices for $x$. Incidentally, if the first primes are $2,3,5$, we fare better by picking $x\equiv 0\pmod {p_1}$ and then there are less forbidden values at each stage, leading to at least
$$\tag1 (p_2-1)(p_3-3)(p_4-5)\cdots (p_n-2n+3)$$
good choices for $x$. While this is a substantial number, we can heuristically expect the smallest good $x$ to be in the order of magnitude $p_1\cdots p_n$ divided by $(1)$, i.e., we may expect
$$ x\approx p_1\left(1+\frac1{p_2-1}\right)\left(1+\frac3{p_3-3}\right)\left(1+\frac5{p_4-5}\right)\cdots\left(1+\frac{2n-3}{p_n-2n+3}\right)$$
to be achievable (thereby obtaining a heuristic estimate as answer to Q3)..
If the $p_i$ are the $25$ primes below $100$, this estimate is $\approx 1.8\cdot 10^9$, for the $168$ primes below $1000$, it is $\approx 2.6\cdot 10^{39}$, so from a practical point of view still unfeasibly large. These heuristic estimates make no claim about the actually smallest possible $x$ for these cases. In fact, by brute force, one finds that that $x=545408$ works for the 25 primes $<100$ and we need to increase $x$ to $62947$ to also work for $p=101$ (and in fact up to $p=137$).
However, in other cases, this estimate may be more promising, namely if we deal with only two or three primes (and not the smallest): Now we can expect some $x\approx p_1\left(1+\frac1{p_2-1}\right)\left(1+\frac3{p_3-3}\right)<p_1+5$ to work (which is of course $\ll p_1p_2$, not to mention $\ll p_1p_2p_3$). In fact, for $n=2$, it is certain that $x=p_1$ works (but is probably not the smallest). It is quite often the case that $x=\lceil\sqrt{p_{n-1}}\rceil$ is worth looking into. The proportion $\ge \left(1-\frac1{p_2}\right)\left(1-\frac1{p_3}\right)$ is typically close enough to $1$ to make it a promising strategy to simply try values for $x$ one by one starting from $\lceil\sqrt{p_{n-1}}\rceil$ upwards and check if the $x^2\bmod {p_i}$ are distinct, rather than following the Chinese Remainder Theorem.
Q2. The estimates made under Q1 make it implausible that requiring $x<N$ allows a solution with a single query.
However, we shall see that two queries always suffice.
To also deal with Q4 along the way, let us pick the first query $x_1$ such that $x_1^2<N$. Then all $p_i>x_1^2$ will lead to the same reply $r_1=x_1^2\bmod p_i=x_1^2$, and in that case we have to pick $x_2$ such that we can distinguish between all primes between $x_1^2$ and $N$.
So if A's first reply $r_1$ is $x_1^2$, we may pick $x_2=\lceil\sqrt{p_{n-1}}\rceil$ (anything smaller cannot tell $p_{n-1}$ from $p_n$) and will either have $r_2=x_2^2$, in which case $p_n$ must be the answer, or $r_2<x_2^2$ and we know that $p$ divides $x_2^2-r_2$ and is $>r_2$ (and $>x_1^2$). A simple strategy to guarantee that only one such $p$ exists for each valid $r_2$, is to ensure that $x_2^2-r_2$ cannot have two prime divisors $>x_1^2$ (and so our guess will simply be the largest prime divisor of $x_2^2-r_2$). For this, it certainly suffices to pick $$\tag2x_1>\sqrt[4]{p_{n-1}}.$$
But what if $r_2< x_1^2$? Then $p$ must be a prime divisor of $x_1^2-r_2$ and must be $>r_2$. Clearly, the product of theses candidate primes is $<x_1^2$ and so even the conservative CRT estimate tells us that there exists a "good" $x_2$ below $x_1^2$, so if we take $(2)$ into account, $x_2<\sqrt {p_{n-1}}<\sqrt N$.
From a practical perspective, we can make the search for $x_2$ simpler by making $x_1$ divisible by many small primes without making it significantly larger. For manageable sizes of $N$, this may help us guarantee that $x_1^2-r_1$ has only very few and not too small prime factors (except when $r_1=0$), thereby making the search for $x_2$ simpler.
For example, with $N=10^9$, we could pick $x_1=210=2\cdot 3\cdot 5\cdot 7$ (the first primorial $>\sqrt[4]{10^9}$). The case $r_1=0$ is handled by $x_2=3$, as $9\bmod2=1$, $9\bmod3=0$, $9\bmod 5=4$, $9\bmod 7=2$ are distinct. The case $r_1=44100$ is handled by $x_2=\lceil\sqrt{10^9}\rceil = 31623$. All other $r_1$ lead to at most three prime factors as already $11\cdot 13\cdot 17\cdot 19>44100$ and are therefore readily dealt with. In fact, for $r_1=1$, we can take $x_2=5$ to tell $11$, $19$, and $247$ apart (please check the factorization of $x_1^2-r_1$ for this case and the cases below); for $r_1=4$, we can pick $x_2=4$ to tell $13$ and $53$ apart; for $r_1=2$ we can take $x_2=5$ to tell $17$ and $1297$ apart; for $r_1=9$ we can take $x_2=5$ to tell $23$ and $71$ apart; for $r_1=20$, it is already clear that $29$ is the solution; for all other remainders $r_1$, there are at most two candidate primes (as $31\cdot 37\cdot 41>44100$) and hence querying the smallest prime factor of $x_1^2-r_1$ exceeding $r_1$ will work.
Best Answer
Usually "rational integer" and "rational prime" is terminology thrown around in algebraic number theory to mean integer of $\mathbb{Q}$ and prime of (the ring of integers of) $\mathbb{Q}$, i.e. elements of $\mathbb{Z}$ or primes in $\mathbb{Z}$. This terminology is used to differentiate between the term algebraic integer, which will often be said without the algebraic preceding it, and the term prime which might refer to a prime ideal in the ring of integers of a number field.