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
320
Note: 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. # http://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 125 Note 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 );;
}
}
Python3def 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 100 Time 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;
}
Javaclass 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 );;
}
}
Python3import 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 10 Time 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
How do you list all the factors of a number in Python?
How to compute all the factors of a given number in Python. we define a function getFactors() which takes a number as input and returns a list of factors;. this function initially creates an empty list;. the function then iterates through number 1 to n using the built-in function range() ;.
How do you find all the factors of a number?
Finding Factors Quickly
Establish the number you want to find the factors of, for example 24. Find two more numbers that multiply to make 24. In this case, 1 x 24 = 2 x 12 = 3 x 8 = 4 x 6 = 24. This means the factors of 24 are 1, 2, 3, 4, 6, 8, 12 and 24.
How do you find the factors of a number efficiently in Python?
Efficient method to find factors of a number. Loop from 1 to sqrt(x) , call it i.. If x % i == 0 , then add i to the list of factors.. Now if x % i == 0 , we can say for sure that, x/i is also a factor of x . So, add x/i to the list of factors. ... . There is one catch in the above step. What if i is same as x/i ?.
What is factor in Python?
The factor of any number is a whole number which exactly divides the number into a whole number without leaving any remainder. For example, 3 is a factor of 9 because 3 divides 9 evenly leaving no remainder.
|