Prime Factorization (Trial Division)

Decomposes n into its prime factors by dividing out each candidate 2…√n; whatever remains above 1 is itself prime.