Shall I take the cailed square root of n to test for a prime?

Question

Algorithm:

1. square root of $n$
2. test all primes lower than the square root of $n$ if they go evenly up into $n$; if not, $n$ is a prime

But do I have to take ceil$(n)$ or floor$(n)$ as the square root?

Answer 1

Don't have to take the square root.

If you are testing a series of primes p, stop when n/p < p.

Answer 2

You have to check for primes only up to floor$(\sqrt n)$.

That's because if $p>\sqrt n$ and $pq=n$, then $q<\sqrt n<p$,

so you would have found a factor of $n$ before you got up to testing $p$ dividing $n$.