Source Code
# Python Program to find the factors of a number # This function computes the factor of the argument passed def print_factors(x): print("The factors of",x,"are:") for i in range(1, x + 1): if x % i == 0: print(i) num = 320 print_factors(num)Output
The factors of 320 are: 1 2 4 5 8 10 16 20 32 40 64 80 160 320Note: To find the factors of another number, change the value of num.
In this program, the number whose factor is to be found is stored in num, which is passed to the print_factors() function. This value is assigned to the variable x in print_factors().
In the function, we use the for loop to iterate from i equal to x. If x is perfectly divisible by i, it's a factor of x.
Here is an example if you want to use the primes number to go a lot faster. These lists are easy to find on the internet. I added comments in the code.
# //primes.utm.edu/lists/small/10000.txt # First 10000 primes _PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, # Mising a lot of primes for the purpose of the example ) from bisect import bisect_left as _bisect_left from math import sqrt as _sqrt def get_factors(n): assert isinstance(n, int), "n must be an integer." assert n > 0, "n must be greather than zero." limit = pow(_PRIMES[-1], 2) assert n <= limit, "n is greather then the limit of {0}".format(limit) result = set((1, n)) root = int(_sqrt(n)) primes = [t for t in get_primes_smaller_than(root + 1) if not n % t] result.update(primes) # Add all the primes factors less or equal to root square for t in primes: result.update(get_factors(n/t)) # Add all the factors associted for the primes by using the same process return sorted(result) def get_primes_smaller_than(n): return _PRIMES[:_bisect_left(_PRIMES, n)]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 125Note that this problem is different from finding all prime factors.
A Naive Solution would be to iterate all the numbers from 1 to n, checking if that number divides n and printing it. Below is a program for the same:
C++
#include <iostream>
using namespace std;
void printDivisors(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
cout <<" " << i;
}
int main()
{
cout <<"The divisors of 100 are: \n";
printDivisors(100);
return 0;
}
C
#include<stdio.h>
void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
printf("%d ",i);
}
int main()
{
printf("The divisors of 100 are: \n");
printDivisors(100);
return 0;
}
Java
class Test
{
static void printDivisors(int n)
{
for (int i=1;i<=n;i++)
if (n%i==0)
System.out.print(i+" ");
}
public static void main(String args[])
{
System.out.println("The divisors of 100 are: ");
printDivisors(100);;
}
}
Python3
def printDivisors(n) :
i = 1
while i <= n :
if (n % i==0) :
print (i,end=" ")
i = i + 1
print ("The divisors of 100 are: ")
printDivisors(100)
C#
using System;
class GFG {
static void printDivisors(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
Console.Write( i + " ");
}
public static void Main()
{
Console.Write("The divisors of",
" 100 are: ");
printDivisors(100);;
}
}
PHP
<?php
function printDivisors($n)
{
for ($i = 1; $i <= $n; $i++)
if ($n % $i == 0)
echo $i," ";
}
echo "The divisors of 100 are:\n";
printDivisors(100);
?>
Javascript
<script>
function printDivisors(n)
{
for (i=1;i<=n;i++)
if (n%i==0)
document.write(i+ " ");
}
document.write("The divisors of 100 are:" + "<br>");
printDivisors(100);
</script>
Output:
The divisors of 100 are: 1 2 4 5 10 20 25 50 100Time Complexity : O(n)
Auxiliary Space : O(1)
Can we improve the above solution?
If we look carefully, all the divisors are present in pairs. For example if n =
100, then the various pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10)
Using this fact we could speed up our program significantly.
We, however, have to be careful if there are two equal divisors as in the case of (10, 10). In such case, we’d print only one of them.
Below is an implementation for the same:
C++
#include <iostream>
#include <math.h>
using namespace std;
void printDivisors(int n)
{
for (int i=1; i<=sqrt(n); i++)
{
if (n%i == 0)
{
if (n/i == i)
cout <<" "<< i;
else
cout << " "<< i << " " << n/i;
}
}
}
int main()
{
cout <<"The divisors of 100 are: \n";
printDivisors(100);
return 0;
}
C
#include <stdio.h>
#include <math.h>
void printDivisors(int n)
{
for (int i=1; i<=sqrt(n); i++)
{
if (n%i == 0)
{
if (n/i == i)
printf("%d ", i);
else
printf("%d %d ", i, n/i);
}
}
}
int main()
{
printf("The divisors of 100 are: \n");
printDivisors(100);
return 0;
}
Java
class Test
{
static void printDivisors(int n)
{
for (int i=1; i<=Math.sqrt(n); i++)
{
if (n%i==0)
{
if (n/i == i)
System.out.print(" "+ i);
else
System.out.print(i+" " + n/i + " " );
}
}
}
public static void main(String args[])
{
System.out.println("The divisors of 100 are: ");
printDivisors(100);;
}
}
Python3
import math
def printDivisors(n) :
i = 1
while i <= math.sqrt(n):
if (n % i == 0) :
if (n / i == i) :
print (i,end=" ")
else :
print (i , int(n/i), end=" ")
i = i + 1
print ("The divisors of 100 are: ")
printDivisors(100)
C#
using System;
class GFG {
static void printDivisors(int n)
{
for (int i = 1; i <= Math.Sqrt(n);
i++)
{
if (n % i == 0)
{
if (n / i == i)
Console.Write(i + " ");
else
Console.Write(i + " "
+ n / i + " ");
}
}
}
public static void Main()
{
Console.Write("The divisors of "
+ "100 are: \n");
printDivisors(100);
}
}
PHP
<?php
function printDivisors($n)
{
for ($i = 1; $i <= sqrt($n); $i++)
{
if ($n%$i == 0)
{
if ($n / $i == $i)
echo $i," ";
else
echo $i," ", $n/$i," ";
}
}
}
echo "The divisors of 100 are: \n";
printDivisors(100);
?>
Javascript
<script>
function printDivisors(n)
{
for(let i = 1; i <= Math.sqrt(n); i++)
{
if (n % i == 0)
{
if (parseInt(n / i, 10) == i)
document.write(i);
else
document.write(i + " " +
parseInt(n / i, 10) + " ");
}
}
}
document.write("The divisors of 100 are: </br>");
printDivisors(100);
</script>
Output:
The divisors of 100 are: 1 100 2 50 4 25 5 20 10Time Complexity: O(sqrt(n))
Auxiliary Space : O(1)
However there is still a minor problem in the solution, can you guess?
Yes! the output is not in a sorted fashion which we had got using the brute-force technique. Please refer below for an O(sqrt(n)) time solution that prints divisors in sorted order.
Find all divisors of a natural number | Set
2
This article is contributed by Ashutosh Kumar. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above