Actually you only need to test primes up to the square root of the number you are checking. Numbers up to half the size could include divisors with prime factors you have already checked.
I must be missing something... A number that's got a whole number square root can't be prime, by definition.
Clearly, but you still can check
prime numbers up to the square root of the number. Say the square root is the irrational number 7.94... . Then you would only need to test primes up to and including 7.
