As requested I'm posting this an answer. I wrote a short sage script to check the primality of numbers of the form $10^n+333$ where $n$ is in the range $[4,2000]$. I found that the following values of $n$ give rise to prime numbers:
$$4,5,6,12,53,222,231,416.$$
Edit 3: I stopped my laptop's search between 2000 and 3000, since it hadn't found anything in 20 minutes. I wrote a quick program to check numbers of the form $10^n+3*10^i+33$. Here are a couple
- 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000033
- 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000300033
- 100000000000000000000000000000000000000000000000000000300000000000000000000000000000000000000033
- 100000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000033
- 100000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000033
- 10000000000000000000000000000000003000000033
- 10000000000000000000000000000030000000000033
- 10000000000000000000000030000000000000000033
- 10000000003000000000000000000000000000000033
There seemed to be plenty of numbers of this form and presumably I could find more if I checked some of the other possible forms as outlined by dr jimbob.
Note: I revised the post a bit after jimbob pointed out I was actually looking for primes that didn't quite fit the requirements.
Edit 4: As requested here are the sage scripts I used.
To check if $10^n+333$ was prime:
for n in range(0,500):
k=10^n+333
if(is_prime(k)):
print n
And to check for numbers of the form $10^n+3*10^i+33$:
for n in range(0,500):
k=10^n+33
for i in range(2,n):
l=k+3*10^i
if(is_prime(l)):
print l
Mark Bennet already suggested looking at the numbers as geometric series, so I'll use a slightly different approach. Instead of writing the squares like that, try writing them as follows:
$$\begin{align} 15&.999\ldots = 16 \\ 1155&.999\ldots = 1156 \\ 111555&.999\ldots = 111556 \\ \vdots\end{align}$$
These numbers can be expressed as a sum of three numbers, as follows:
$$\begin{align} 111111&.111\ldots \\ 444&.444\ldots \\ 0&.444\ldots \\ \hline 111555&.999\ldots \end{align}$$
Since $1/9 = 0.111\ldots$, we get
$$\begin{align} 111111&.111\ldots = \frac{1}{9} \cdot 10^{2k} \\ 444&.444\ldots = \frac{1}{9} \cdot 4 \cdot 10^k \\ 0&.444\ldots = \frac{1}{9} \cdot 4 \\ \hline 111555&.999\ldots = \frac{1}{9} \left(10^{2k} + 4 \cdot 10^k + 4\right). \end{align}$$
But this can be written as a square:
$$\frac{1}{9} \left(10^{2k} + 4 \cdot 10^k + 4\right) = \left(\frac{10^k + 2}{3}\right)^2.$$
Since $10^k + 2$ is always divisible by $3$, this is indeed the square of an integer.
Best Answer
We sort of need the link between prime factorization and the number of positive divisors. If $n$ has the prime factorization $p_1^{a_1}\cdots p_k^{a_k}$ then the number of positive factors of $n$ is $\prod (a_i+1)$. In particular the number of divisors is odd iff $n$ is a perfect square.
The fact that the number of divisors is odd iff our number is a perfect square can also be done in a formula-free way by a pairing argument. Any divisor $d$ of $n$ can be paired with the divisor $n/d$, which is different from $d$ unless $d=\sqrt{n}$.
Since $n$ ends in $0$ it has $2$ and $5$ and possibly others as prime factors. But $15$ gives very few possibilities: just two $2$'s and four $5$'s, or the other way around.
Remark: High school level? Hard to decide. Certainly every high school student who takes contests seriously is familiar with these facts. And, at least in the fairly recent past, Russian high school students took contests very seriously.