All Divisors of a number

PHOTO EMBED

Sun Feb 06 2022 05:06:01 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #mathematics #lecture #gfg #geeksforgeeks #efficientmethod #naivemethod #factors #divisors

// Efficient Code with Sorted Order

	static void printDivisors(int n)
	{
		int i = 1;
      	// Print all divisors from 1(inlcusive) to sqrt(n) (exclusive)
		for(i=1; i*i < n; i++)
		{
			if(n % i == 0)
			{
				System.out.print(i+" ");
			}
		}
		// Print all divisors from sqrt(n)(inlcusive) to n (inclusive)
		for(; i >= 1; i--)
		{
			if(n % i == 0)
			{
				System.out.print((n / i)+" ");
			}
		}
	}

//Efficient Code : Time Complexity: O(sqrt(n)) , Auxiliary Space : O(1)

	static void printDivisors(int n)
	{
		for(int i=1; i*i <= n; i++)
		{
			if(n % i == 0)
			{
				System.out.print(i+" ");

				if(i != n / i)
					System.out.print((n / i)+" ");					
			}
		}
	}

// Naive Solution : Time Complexity : O(n) , Auxiliary Space : O(1)

	static void printDivisors(int n)
	{
		for (int i=1;i<=n;i++)
			if (n%i==0)
				System.out.print(i+" ");
	}
content_copyCOPY

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)