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)]
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. Given an array of integers. We are required to write a program to print the number of factors of every element of the given array.
Examples:
Input: 10 12 14
Output: 4 6 4
Explanation: There are 4 factors of 10 (1, 2,
5, 10) and 6 of 12 and 4 of 14.
Input: 100 1000 10000
Output: 9 16 25
Explanation: There are 9 factors of 100 and
16 of 1000 and 25 of 10000. Simple Approach: A simple approach will be to run two nested loops. One for traversing the array and other for calculating all factors of elements of array.
Time Complexity: O( n * n)
Auxiliary Space: O( 1 )
Efficient
Approach: We can optimize the above approach by optimizing the number of operations required to calculate the factors of a number. We can calculate the factors of a number n in sqrt(n) operations using this approach.
Time Complexity: O( n * sqrt(n))
Auxiliary Space: O( 1 )
Best Approach: If you go through number theory,
you will find an efficient way to find the number of factors. If we take a number, say in this case 30, then the prime factors of 30 will be 2, 3, 5 with count of each of these being 1 time, so total number of factors of 30 will be (1+1)*(1+1)*(1+1) = 8.
Therefore, the general formula of total number of factors of a given number will be:
Factors = (1+a1) * (1+a2) * (1+a3) * … (1+an) where a1, a2, a3 …. an are count of distinct prime factors of n.
Let’s take another example to make things more clear.
Let the number be 100 this time,
So 100 will have 2, 2, 5, 5. So the count of distinct prime factors of 100 are 2, 2. Hence number of factors will be (2+1)*(2+1) = 9.
Now, the best way to find the prime factorization will be to store the sieve of prime factors initially. Create the sieve in a way that it stores the smallest primes factor that divides itself. We can modify the Sieve of Eratostheneses to
do this. Then simply for every number find the count of prime factors and multiply it to find the number of total factors .
Below is the implementation of above approach.
C++#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000001;
int factor[MAX] = { 0 };
void generatePrimeFactors()
{
factor[1] = 1;
for (int i = 2; i < MAX; i++)
factor[i] = i;
for
(int i = 4; i < MAX; i += 2)
factor[i] = 2;
for (int i = 3; i * i < MAX; i++) {
if (factor[i] == i) {
for (int j = i * i; j < MAX; j += i) {
if (factor[j] == j)
factor[j] = i;
}
}
}
}
int calculateNoOfFactors(int n)
{
if (n == 1)
return 1;
int ans = 1;
int
dup = factor[n];
int c = 1;
int j = n / factor[n];
while (j != 1) {
if (factor[j] == dup)
c += 1;
else {
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
j = j / factor[j];
}
ans = ans * (c + 1);
return ans;
}
int main()
{
generatePrimeFactors();
int a[] = { 10, 30, 100, 450, 987 };
int
q = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < q; i++)
cout << calculateNoOFactors(a[i]) << " ";
return 0;
}
Javaimport java.util.*;
class GFG {
static int MAX = 1000001;
static int factor[];
static void generatePrimeFactors()
{
factor[1] = 1;
for
(int i = 2; i < MAX; i++)
factor[i] = i;
for (int i = 4; i < MAX; i += 2)
factor[i] = 2;
for (int i = 3; i * i < MAX; i++) {
if (factor[i] == i) {
for (int j = i * i; j < MAX; j += i) {
if (factor[j] == j)
factor[j] = i;
}
}
}
}
static
int calculateNoOfFactors(int n)
{
if (n == 1)
return 1;
int ans = 1;
int dup = factor[n];
int c = 1;
int j = n / factor[n];
while (j != 1) {
if (factor[j] == dup)
c += 1;
else {
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
j = j / factor[j];
}
ans = ans * (c + 1);
return ans;
}
public static void main(String[] args)
{
factor = new int[MAX];
factor[0] = 0;
generatePrimeFactors();
int
a[] = { 10, 30, 100, 450, 987 };
int q = a.length;
for (int i = 0; i < q; i++)
System.out.print(calculateNoOFactors(a[i]) + " ");
}
}
Python3MAX = 1000001;
factor =
[0]*(MAX + 1);
def generatePrimeFactors():
factor[1] = 1;
for i in range(2,MAX):
factor[i] = i;
for i in range(4,MAX,2):
factor[i] = 2;
i =
3;
while(i * i < MAX):
if (factor[i] == i):
j = i * i;
while(j < MAX):
if (factor[j] == j):
factor[j] = i;
j += i;
i+=1;
def calculateNoOfFactors(n):
if
(n == 1):
return 1;
ans = 1;
dup = factor[n];
c = 1;
j = int(n / factor[n]);
while (j > 1):
if (factor[j] == dup):
c += 1;
else:
dup =
factor[j];
ans = ans * (c + 1);
c = 1;
j = int(j / factor[j]);
ans = ans * (c + 1);
return ans;
if __name__ == "__main__":
generatePrimeFactors()
a =
[10, 30, 100, 450, 987]
q = len(a)
for i in range (0,q):
print(calculateNoOFactors(a[i]),end=" ")
C#using System;
class GFG {
static int MAX = 1000001;
static
int[] factor;
static void generatePrimeFactors()
{
factor[1] = 1;
for (int i = 2; i < MAX; i++)
factor[i] = i;
for (int i = 4; i < MAX; i += 2)
factor[i] = 2;
for (int i = 3; i * i < MAX; i++)
{
if (factor[i] == i)
{
for (int j = i * i;
j < MAX; j += i)
{
if
(factor[j] == j)
factor[j] = i;
}
}
}
}
static int calculateNoOfFactors(int n)
{
if (n == 1)
return 1;
int ans = 1;
int dup = factor[n];
int c = 1;
int j = n / factor[n];
while (j != 1) {
if (factor[j] == dup)
c += 1;
else
{
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
j = j / factor[j];
}
ans = ans * (c + 1);
return ans;
}
public static void Main()
{
factor = new int[MAX];
factor[0] = 0;
generatePrimeFactors();
int[] a = { 10, 30, 100, 450, 987 };
int q = a.Length;
for (int
i = 0; i < q; i++)
Console.Write(
calculateNoOFactors(a[i])
+ " ");
}
}
PHP<?php
$MAX = 1000001;
$factor = array_fill(0, $MAX + 1, 0);
function generatePrimeFactors()
{
global $factor;
global $MAX;
$factor[1] = 1;
for ($i
= 2; $i < $MAX; $i++)
$factor[$i] = $i;
for ($i = 4; $i < $MAX; $i += 2)
$factor[$i] = 2;
for ($i = 3; $i * $i < $MAX; $i++)
{
if
($factor[$i] == $i)
{
for ($j = $i * $i;
$j < $MAX; $j += $i)
{
if ($factor[$j] == $j)
$factor[$j] = $i;
}
}
}
}
function calculateNoOfFactors($n)
{
global $factor;
if ($n == 1)
return 1;
$ans = 1;
$dup = $factor[$n];
$c = 1;
$j = (int)($n / $factor[$n]);
while ($j != 1)
{
if ($factor[$j] == $dup)
$c += 1;
else
{
$dup = $factor[$j];
$ans = $ans * ($c + 1);
$c = 1;
}
$j = (int)($j / $factor[$j]);
}
$ans = $ans * ($c
+ 1);
return $ans;
}
generatePrimeFactors();
$a = array(10, 30, 100, 450, 987);
$q = sizeof($a);
for ($i = 0; $i < $q; $i++)
echo calculateNoOFactors($a[$i]) . " ";
?>
Javascript<script>
var MAX = 1000001;
var factor = [];
function
generatePrimeFactors() {
factor[1] = 1;
for (i = 2; i < MAX; i++)
factor[i] = i;
for (i = 4; i < MAX; i += 2)
factor[i] = 2;
for (i = 3; i * i < MAX; i++)
{
if (factor[i] == i)
{
for (j = i * i; j < MAX; j += i)
{
if (factor[j] == j)
factor[j] = i;
}
}
}
}
function calculateNoOfFactors(n)
{
if (n == 1)
return 1;
var ans = 1;
var dup = factor[n];
var c = 1;
var j = n / factor[n];
while (j != 1)
{
if (factor[j] == dup)
c += 1;
else
{
dup = factor[j];
ans = ans * (c + 1);
c = 1;
}
j = j / factor[j];
}
ans = ans * (c + 1);
return ans;
}
factor = Array(MAX).fill(0);
factor[0] = 0;
generatePrimeFactors();
var a = [ 10, 30, 100, 450, 987 ];
var q = a.length;
for (i = 0; i < q; i++)
document.write(calculateNoOFactors(a[i]) + " ");
</script>
Output:
4 8 9 18 8 Time Complexity: O(n * log(max(number))), where n is total number of elements in the array and max(number) represents the maximum number
in the array.
Auxiliary Space: O(n) for calculating the sieve.
This article is contributed by Raja Vikramaditya. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments
if you find anything incorrect, or you want to share more information about the topic discussed above.
How do you factor a number efficiently?
Best Approach: If you go through number theory, you will find an efficient way to find the number of factors. If we take a number, say in this case 30, then the prime factors of 30 will be 2, 3, 5 with count of each of these being 1 time, so total number of factors of 30 will be (1+1)*(1+1)*(1+1) = 8.
How do you check factors in Python?
Source Code
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() .
|
