All Divisors of a number
Sun Feb 06 2022 05:06:01 GMT+0000 (Coordinated Universal Time)
Saved by @Uttam #java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #factors #divisors
Find all factors of a natural number Given a natural number n, print all distinct divisors of it. Examples: Input : n = 10 Output: 1 2 5 10 Input: n = 100 Output: 1 2 4 5 10 20 25 50 100 Input: n = 125 Output: 1 5 25 125 Naive solution: ----------------- A Naive Solution would be to iterate all the numbers from 1 to n, checking if that number divides n and printing it. Efficient Solution: ------------------- 1.) Divisors always appear in pairs 30 : (1,30) , (2,15) , (3,10) , (5,6) 2.) One of the divisors in every pair is smaller than or equal to sqrt(n) For a pair (x,y) x * y = n Let x be the smaller, i.e; x <= y If x<=y x * x <= n x <= sqrt(n)
Comments