gnomes and lights vs. sieve of Eratosthenes

Question

I was riddled a riddle the other day - a series of gnomes flips a series of light switches. The first gnome flips every switch, the second gnome flips every second switch, the third gnome flips every third switch, etc. This is similar to the sieve of Eratosthenes where instead of flipping a switch, the lights are removed . The first method leaves lights on for the squares, while the second leaves the primes extant (until the nth gnome) - is there thus some connection between squares and primes?

Answer 1

There is a simple criterion for prime numbers using perfect squares.

Let $N>2$ be a positive integer and $n$ be the smallest positive integer with $n^2>N$. Then , $N$ is a prime number, if and only if it has no divisor $d$ with $1<d\le n$.