Question

We can determine whether a number, n, is prime or not by dividing it by every prime whose square is less than or equal to n.

Why does it work?

Answer 1

every non-prime number has a set of prime factors. except if the number is prime itself, in which case its only prime factor is itself. the reason the square comes into place is because for every number the square root is where the factors "reflect" in a sense . so like take the factors of a number like 12. it has the factors 1,2,3,4,6,12 but you only have to check for 1,2,3 because 3*4 is 12 and 2*6 is 12 so you know that if those numbers arent there then there cant be any other factors.

Answer 2

Can you tell me who discover this method?

Answer 3

I think it was Euclid. but it probably goes back much further without being documented.

Answer 4

Im not sure about that though.

Answer 5

Okay, thanks!

Answer 6

No problem!