Given a number n, the task of the programmer is to print the factors of the number in such a way that they occur in pairs. A pair signifies that the product of the pair should result in the number itself.
Examples:
Input : 24
Output : 1*24
2*12
3*8
4*6
Input : 50
Output : 1*50
2*25
5*10
The simplest approach for this program is that we run a loop from 1 to the square root of N and print and print ‘i’ and ‘N%i’ if the number N is dividing ‘i’.
The mathematical reason why we run the loop till square root of N is given below:
If a*b = N where 1 < a ≤ b < N
N = ab ≥ a^2 ⇔ a^2 ≤ N ⇔ a ≤ √N
C++
#include <iostream>
using namespace std;
void printPFsInPairs(int n)
{
for (int i = 1; i * i <= n; i++)
if (n % i == 0)
cout << i << "*" << n / i << endl;
}
int main()
{
int n = 24;
printPFsInPairs(n);
return 0;
}
|
Java
public class GEE {
static void printPFsInPairs(int n)
{
for (int i = 1; i * i <= n; i++)
if (n % i == 0)
System.out.println(i + "*" + n / i);
}
public static void main(String[] args)
{
int n = 24;
printPFsInPairs(n);
}
}
|
Python 3
def printPFsInPairs(n):
for i in range(1, int(pow(n, 1 / 2))+1):
if n % i == 0:
print(str(i) +"*"+str(int(n / i)))
n = 24
printPFsInPairs(n)
|
C#
using System;
public class GEE {
static void printPFsInPairs(int n)
{
for (int i = 1; i * i <= n; i++)
if (n % i == 0)
Console.Write(i + "*" + n / i + "\n");
}
public static void Main()
{
int n = 24;
printPFsInPairs(n);
}
}
|
Javascript
<script>
function printPFsInPairs(n)
{
for (let i = 1; i * i <= n; i++)
if (n % i == 0)
document.write(i + "*" + parseInt(n / i) + "<br>");
}
let n = 24;
printPFsInPairs(n);
</script>
|
PHP
<?php
function printPFsInPairs($n)
{
for ($i = 1; $i*$i <= $n; $i++)
if ($n % $i == 0)
echo $i."*". $n / $i ."\n";
}
$n = 24;
printPFsInPairs($n);
return 0;
?>
|
Time Complexity: O(sqrt(n)) where n is given number
Auxiliary Space: O(1)
Approach#2: Using for loop
The program first defines a function print_factor_pairs that takes a positive integer num as input. The function generates all factors of num using a list comprehension that loops through all numbers from 1 to the square root of num, and appends the pair (i, num//i) to a list if num is divisible by i. The function then iterates through the list of factor pairs and prints them in the format “i*j”. In the main code, the user inputs a number and calls the print_factor_pairs function with that number as input.
Algorithm
1. Define a function print_factor_pairs that takes a positive integer num as input.
2. Generate all factors of num using a list comprehension that loops through all numbers from 1 to the square root of num, and appends the pair (i, num//i) to a list if num is divisible by i.
3. Iterate through the list of factor pairs and print them in the format “i*j”.
4. In the main code, input a number from the user and call the print_factor_pairs function with that number as input.
C++
#include <iostream>
#include <vector>
using namespace std;
void printFactorPairs(int num) {
vector<pair<int, int>> factors;
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
int factor1 = i;
int factor2 = num / i;
factors.push_back(make_pair(factor1, factor2));
}
}
for (auto pair : factors) {
cout << pair.first << "*" << pair.second << endl;
}
}
int main() {
int num = 24;
printFactorPairs(num);
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.AbstractMap.SimpleEntry;
import java.util.List;
public class GFG {
public static void printFactorPairs(int num) {
List<SimpleEntry<Integer, Integer>> factors = new ArrayList<>();
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
int factor1 = i;
int factor2 = num / i;
factors.add(new SimpleEntry<>(factor1, factor2));
}
}
for (SimpleEntry<Integer, Integer> pair : factors) {
System.out.println(pair.getKey() + "*" + pair.getValue());
}
}
public static void main(String[] args) {
int num = 24;
printFactorPairs(num);
}
}
|
Python3
def print_factor_pairs(num):
factors = [(i, num//i) for i in range(1, int(num**0.5)+1) if num % i == 0]
for pair in factors:
print(f"{pair[0]}*{pair[1]}")
num = 24
print_factor_pairs(num)
|
C#
using System;
using System.Collections.Generic;
public class GFG
{
public static void PrintFactorPairs(int num)
{
List<Tuple<int, int>> factors = new List<Tuple<int, int>>();
for (int i = 1; i * i <= num; i++)
{
if (num % i == 0)
{
int factor1 = i;
int factor2 = num / i;
factors.Add(Tuple.Create(factor1, factor2));
}
}
foreach (var pair in factors)
{
Console.WriteLine(pair.Item1 + "*" + pair.Item2);
}
}
public static void Main()
{
int num = 24;
PrintFactorPairs(num);
}
}
|
Javascript
function printFactorPairs(num) {
const factors = [];
for (let i = 1; i * i <= num; i++) {
if (num % i === 0) {
const factor1 = i;
const factor2 = num / i;
factors.push([factor1, factor2]);
}
}
for (const [factor1, factor2] of factors) {
console.log(factor1 + "*" + factor2);
}
}
const num = 24;
printFactorPairs(num);
|
Time complexity: O(sqrt(num)) because the loop only goes up to the square root of num.
The time complexity of iterating through the list of factor pairs and printing them is O(sqrt(num)) because there are sqrt(num) factor pairs.
Space complexity: O(sqrt(num)) because the list of factor pairs generated by the program has at most sqrt(num) elements.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
