Genau so ist es. Das liegt an der Eindeutigkeit der Primfaktorzerlegung. Deswegen müssen nur Primfaktoren geprüft werden. Wenn eine Zahl beispielsweise nicht durch 2 teilbar ist, kann sie auch nicht durch alle Vielfachen von 2 teilbar sein. So prüft man dann alle Primfaktoren.

Dass man nur alle Primfaktoren bis $\sqrt{n}$ testen muss, liegt daran, dass kein größerer Primfaktor auftreten kann, denn sonst hätte es bereits einen kleineren Primfaktor als Teiler gegeben. Bei der Primfaktorzerlegung hast du also mindestens zwei Faktoren, wenn die Zahl nicht prim ist. Der größte Faktor kann aber nur $\sqrt{n} $ sein.

Siehe dazu auch das Sieb des Eratosthenes.