Given an integer N, the task is to find all the divisors of numbers from 1 to N.
Note: 1 ? N ? 100000
Examples:
Input: N = 2
Output:
1 –>1
2 –>1, 2Input: N = 5
Output:
1 –>1
2 –>1, 2
3 –>1, 3
4 –>1, 2, 4
5 –>1, 5
Naive Approach:
- Iterate over first N natural numbers using a loop variable (say i)
- Iterate over the natural numbers from 1 to i with a loop variable (say j) and check that i % j == 0. Then j is a divisor of the natural number i.
Below is the implementation of the above approach:
C++
// C++ implementation to find all // the divisors of the first N// natural numbers#include <bits/stdc++.h>using namespace std;// Function to find the divisors// of the first N natural numbersvoid factors(int n){ int i, j; cout << "1 -->1\n"; // Loop to find the divisors for (i = 2; i <= n; i++) { cout << i << " -->"; for (j = 1; j <= i / 2; j++) { if (i % j == 0) cout << j << ", "; } cout << i << "\n"; }}// Driver Codeint main(){ int n = 5; factors(n);} |
Java
// Java implementation to find all // the divisors of the first N// natural numbersimport java.io.*;public class GFG{// Function to find the divisors// of the first N natural numbersstatic void factors(int n){ int i, j; System.out.print("1 -->1\n"); // Loop to find the divisors for(i = 2; i <= n; i++) { System.out.print(i + " -->"); for(j = 1; j <= i / 2; j++) { if (i % j == 0) System.out.print(j + ", "); } System.out.print(i + "\n"); }}// Driver Codepublic static void main(String[] args){ int n = 5; factors(n);}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 implementation to find all # the divisors of the first N# natural numbers# Function to find the divisors# of the first N natural numbersdef factors(n): i = 0; j = 0; print("1 -->1"); # Loop to find the divisors for i in range(2, n + 1): print(i, "-->", end = ""); for j in range(1, (i // 2) + 1): if (i % j == 0): print(j, ",", end = ""); print(i, end = "\n"); # Driver Coden = 5;factors(n);# This code is contributed by Code_Mech |
C#
// C# implementation to find all // the divisors of the first N// natural numbersusing System;class GFG{// Function to find the divisors// of the first N natural numbersstatic void factors(int n){ int i, j; Console.Write("1 -->1\n"); // Loop to find the divisors for(i = 2; i <= n; i++) { Console.Write(i + " -->"); for(j = 1; j <= i / 2; j++) { if (i % j == 0) Console.Write(j + ", "); } Console.Write(i + "\n"); }}// Driver Codepublic static void Main(){ int n = 5; factors(n);}}// This code is contributed by Nidhi_biet |
Javascript
<script>// JavaScript implementation to find all // the divisors of the first N// natural numbers// Function to find the divisors// of the first N natural numbersfunction factors(n){ let i, j; document.write("1 -->1<br>"); // Loop to find the divisors for (i = 2; i <= n; i++) { document.write(i + " -->"); for (j = 1; j <= parseInt(i / 2); j++) { if (i % j == 0) document.write(j + ", "); } document.write(i + "<br>"); }}// Driver Codelet n = 5;factors(n);</script> |
Output:
1 -->1 2 -->1, 2 3 -->1, 3 4 -->1, 2, 4 5 -->1, 5
Time Complexity: O(N2)
Auxiliary Space: O(1)
Better Approach:
- Iterate over the first N natural numbers using a loop variable.
- For the number to find its divisors iterate from 2 to that number and check any one of them is a divisor of the given number.
Below is the implementation of the above approach:
C++
// C++ implementation to find all// the divisors of the first// N natural numbers#include <bits/stdc++.h>using namespace std;// Function to find the factors of// the numbers from 1 to Nvoid factors(int n){ int i, j; cout << "1 -->1\n"; // Loop to find the factors // of the first N natural // numbers of the integer for (i = 2; i <= n; i++) { cout << i << " -->"; for (j = 1; j * j <= i; j++) { if (i % j == 0){ cout << j << ", "; if (i / j != j) cout << i/j << ", "; } } cout << "\n"; }}// Driver Codeint main(){ int n = 5; factors(n);} |
Java
// Java implementation to find all// the divisors of the first// N natural numbersimport java.util.*;class GFG{// Function to find the factors of// the numbers from 1 to Nstatic void factors(int n){ int i, j; System.out.print("1 -->1\n"); // Loop to find the factors // of the first N natural // numbers of the integer for (i = 2; i <= n; i++) { System.out.print(i + " -->"); for (j = 1; j * j <= i; j++) { if (i % j == 0) { System.out.print(j + ", "); if (i / j != j) System.out.print(i / j + ", "); } } System.out.print("\n"); }}// Driver Codepublic static void main(String args[]){ int n = 5; factors(n);}}// This code is contributed by Code_Mech |
Python3
# Python3 implementation to find all# the divisors of the first# N natural numbers# Function to find the factors of# the numbers from 1 to Ndef factors(n): print("1 -->1"); # Loop to find the factors # of the first N natural # numbers of the integer for i in range(2, n + 1): print(i, " -->", end = ""); for j in range(1, int(pow(i, 1))): if (i % j == 0): print(j, ", ", end = ""); if (i // j != j): print(i // j, ", ", end = ""); print(end = "\n"); # Driver Codeif __name__ == '__main__': n = 5; factors(n);# This code is contributed by gauravrajput1 |
C#
// C# implementation to find all// the divisors of the first// N natural numbersusing System;class GFG{// Function to find the factors of// the numbers from 1 to Nstatic void factors(int n){ int i, j; Console.Write("1 -->1\n"); // Loop to find the factors // of the first N natural // numbers of the integer for (i = 2; i <= n; i++) { Console.Write(i + " -->"); for (j = 1; j * j <= i; j++) { if (i % j == 0) { Console.Write(j + ", "); if (i / j != j) Console.Write(i / j + ", "); } } Console.Write("\n"); }}// Driver Codepublic static void Main(){ int n = 5; factors(n);}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation to find all// the divisors of the first// N natural numbers// Function to find the factors of// the numbers from 1 to Nfunction factors(n){ let i, j; document.write("1 -->1<br>"); // Loop to find the factors // of the first N natural // numbers of the integer for(i = 2; i <= n; i++) { document.write(i + " -->"); for(j = 1; j * j <= i; j++) { if (i % j == 0) { document.write(j + ", "); if (parseInt(i / j) != j) document.write(parseInt(i/j) + ", "); } } document.write("<br>"); }}// Driver Codelet n = 5;factors(n);// This code is contributed by subhammahato348</script> |
Output:
1 -->1 2 -->1, 2, 3 -->1, 3, 4 -->1, 4, 2, 5 -->1, 5,
Time Complexity: O(N*sqrt(N))
Auxiliary Space: O(1)
As constant extra space is used.
Efficient Approach: The idea is to precompute the factors of the numbers with the help of the Sieve of Eratosthenes. Then finally iterate over the first N natural numbers to find the factors.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // factors of first N natural // numbers #include <bits/stdc++.h>using namespace std;const int MAX = 1e5; // Initialize global divisor vector // array of sequence container vector<int> divisor[MAX + 1]; // Calculate all // divisors of number void sieve() { for (int i = 1; i <= MAX; ++i) { for (int j = i; j <= MAX; j += i) divisor[j].push_back(i); } }// Function to find the // factors of first n// natural numbersvoid findNFactors(int n){ for(int i = 1; i <= n; i++){ cout << i << "-->"; for (auto &divi: divisor[i]){ cout << divi << ", "; } cout << "\n"; }}// Driver Codeint main(){ int n = 5; sieve(); // Function Call findNFactors(n);} |
Java
// Java implementation to find the // factors of first N natural // numbers import java.util.*;class GFG{static int MAX = (int) 1e5; // Initialize global divisor vector // array of sequence container static Vector<Integer> []divisor = new Vector[MAX + 1]; // Calculate all // divisors of number static void sieve() { for (int i = 1; i <= MAX; ++i) { for (int j = i; j <= MAX; j += i) divisor[j].add(i); } }// Function to find the // factors of first n// natural numbersstatic void findNFactors(int n){ for(int i = 1; i <= n; i++) { System.out.print(i+ "-->"); for (int divi: divisor[i]) { System.out.print(divi+ ", "); } System.out.print("\n"); }}// Driver Codepublic static void main(String[] args){ int n = 5; for (int i = 0; i < divisor.length; i++) divisor[i] = new Vector<Integer>(); sieve(); // Function Call findNFactors(n);}}// This code is contributed by Princi Singh |
Python3
# Python3 program to find the factors# of first N natural numbersMAX = 100001# Initialize divisor list(array)# of sequence containerdivisor = [[] for x in range(MAX)] # Calculate all divisors of a numberdef sieve(): for i in range(1, MAX): for j in range(i, MAX, i): divisor[j].append(i)# Function to find the factors of# first n natural numbersdef findNFactors (n): for i in range(1, n + 1): print(i, " --> ", end = '') for divi in divisor[i]: print(divi, ", ", end = '') print()# Driver codeif __name__ == '__main__': n = 5 sieve() # Function call findNFactors(n)# This code is contributed by himanshu77 |
C#
// C# implementation to find the // factors of first N natural // numbers using System;using System.Collections.Generic; public class GFG{ static int MAX = (int) 1e5; // Initialize global divisor vector // array of sequence container static List<int> []divisor = new List<int>[MAX + 1]; // Calculate all // divisors of number static void sieve() { for (int i = 1; i <= MAX; ++i) { for (int j = i; j <= MAX; j += i) divisor[j].Add(i); } } // Function to find the // factors of first n// natural numbersstatic void findNFactors(int n){ for(int i = 1; i <= n; i++) { Console.Write(i+ "-->"); foreach (int divi in divisor[i]) { Console.Write(divi+ ", "); } Console.Write("\n"); }} // Driver Codepublic static void Main(String[] args){ int n = 5; for (int i = 0; i < divisor.Length; i++) divisor[i] = new List<int>(); sieve(); // Function Call findNFactors(n);}} // This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript implementation to find the // factors of first N natural // numbers var MAX = 100000; // Initialize global divisor vector // array of sequence container var divisor = Array.from(Array(MAX+1),()=> Array(0));// Calculate all // divisors of number function sieve() { for (var i = 1; i <= MAX; ++i) { for (var j = i; j <= MAX; j += i) divisor[j].push(i); } }// Function to find the // factors of first n// natural numbersfunction findNFactors(n){ for(var i = 1; i <= n; i++){ document.write( i + "-->"); for (var j =0; j< divisor[i].length;j++){ document.write( divisor[i][j] + ", "); } document.write( "<br>"); }}// Driver Codevar n = 5;sieve();// Function CallfindNFactors(n);// This code is contributed by noob2000.</script> |
Output:
1-->1, 2-->1, 2, 3-->1, 3, 4-->1, 2, 4, 5-->1, 5,
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
