Prime Trivia

“First – and this begins to get technical – note that if a number is a composite, such as n=ab, then a and b cannot both exceed √n. For example, with the composite “21” – 21=3×7 – only 7 is bigger than √21 = 4.58. Therefore, he determined that any composite integer n is divisible by a prime p that does not exceed √n”

So how might one represent that rule in binary – or how would one relate the square root of a composite number to a smaller prime number? Is there a bit of bit shuffling magic possible???

It follows from this that to test for primes it is only necessary to divide a number by numbers less than or equal to its square root. To find primes from 2 to 30, then, we need only use the fact that √30 is less than 7, and work with the primes 2, 3 and 5.