Least prime factor of numbers till n
Given a number n, print least prime factors of all numbers from 1 to n. The least prime factor of an integer n is the smallest prime number that divides the number. The least prime factor of all even numbers is 2. A prime number is its own least prime factor (as well as its own greatest prime factor).
Note: We need to print 1 for 1.
Example :
Input : 6 Output : Least Prime factor of 1: 1 Least Prime factor of 2: 2 Least Prime factor of 3: 3 Least Prime factor of 4: 2 Least Prime factor of 5: 5 Least Prime factor of 6: 2
We can use a variation of sieve of Eratosthenes to solve the above problem.
- Create a list of consecutive integers from 2 through n: (2, 3, 4, …, n).
- Initially, let i equal 2, the smallest prime number.
- Enumerate the multiples of i by counting to n from 2i in increments of i, and mark them as having least prime factor as i (if not already marked). Also mark i as least prime factor of i (i itself is a prime number).
- Find the first number greater than i in the list that is not marked. If there was no such number, stop. Otherwise, let i now equal this new number (which is the next prime), and repeat from step 3.
Below is the implementation of the algorithm, where least_prime[] saves the value of the least prime factor corresponding to the respective index.
C++
// C++ program to print the least prime factors // of numbers less than or equal to // n using modified Sieve of Eratosthenes #include<bits/stdc++.h> using namespace std; void leastPrimeFactor( int n) { // Create a vector to store least primes. // Initialize all entries as 0. vector< int > least_prime(n+1, 0); // We need to print 1 for 1. least_prime[1] = 1; for ( int i = 2; i <= n; i++) { // least_prime[i] == 0 // means it i is prime if (least_prime[i] == 0) { // marking the prime number // as its own lpf least_prime[i] = i; // mark it as a divisor for all its // multiples if not already marked for ( int j = i*i; j <= n; j += i) if (least_prime[j] == 0) least_prime[j] = i; } } // print least prime factor of // of numbers till n for ( int i = 1; i <= n; i++) cout << "Least Prime factor of " << i << ": " << least_prime[i] << "\n" ; } // Driver program to test above function int main() { int n = 10; leastPrimeFactor(n); return 0; } |
Java
// Java program to print the least prime factors // of numbers less than or equal to // n using modified Sieve of Eratosthenes import java.io.*; import java.util.*; class GFG { public static void leastPrimeFactor( int n) { // Create a vector to store least primes. // Initialize all entries as 0. int [] least_prime = new int [n+ 1 ]; // We need to print 1 for 1. least_prime[ 1 ] = 1 ; for ( int i = 2 ; i <= n; i++) { // least_prime[i] == 0 // means it i is prime if (least_prime[i] == 0 ) { // marking the prime number // as its own lpf least_prime[i] = i; // mark it as a divisor for all its // multiples if not already marked for ( int j = i*i; j <= n; j += i) if (least_prime[j] == 0 ) least_prime[j] = i; } } // print least prime factor of // of numbers till n for ( int i = 1 ; i <= n; i++) System.out.println( "Least Prime factor of " + + i + ": " + least_prime[i]); } public static void main (String[] args) { int n = 10 ; leastPrimeFactor(n); } } // Code Contributed by Mohit Gupta_OMG <(0_o)> |
Python 3
# Python 3 program to print the # least prime factors of numbers # less than or equal to n using # modified Sieve of Eratosthenes def leastPrimeFactor(n) : # Create a vector to store least primes. # Initialize all entries as 0. least_prime = [ 0 ] * (n + 1 ) # We need to print 1 for 1. least_prime[ 1 ] = 1 for i in range ( 2 , n + 1 ) : # least_prime[i] == 0 # means it i is prime if (least_prime[i] = = 0 ) : # marking the prime number # as its own lpf least_prime[i] = i # mark it as a divisor for all its # multiples if not already marked for j in range (i * i, n + 1 , i) : if (least_prime[j] = = 0 ) : least_prime[j] = i # print least prime factor # of numbers till n for i in range ( 1 , n + 1 ) : print ( "Least Prime factor of " ,i , ": " , least_prime[i] ) # Driver program n = 10 leastPrimeFactor(n) # This code is contributed # by Nikita Tiwari. |
C#
// C# program to print the least prime factors // of numbers less than or equal to // n using modified Sieve of Eratosthenes using System; class GFG { public static void leastPrimeFactor( int n) { // Create a vector to store least primes. // Initialize all entries as 0. int []least_prime = new int [n+1]; // We need to print 1 for 1. least_prime[1] = 1; for ( int i = 2; i <= n; i++) { // least_prime[i] == 0 // means it i is prime if (least_prime[i] == 0) { // marking the prime number // as its own lpf least_prime[i] = i; // mark it as a divisor for all its // multiples if not already marked for ( int j = i*i; j <= n; j += i) if (least_prime[j] == 0) least_prime[j] = i; } } // print least prime factor of // of numbers till n for ( int i = 1; i <= n; i++) Console.WriteLine( "Least Prime factor of " + i + ": " + least_prime[i]); } // Driver code public static void Main () { int n = 10; // Function calling leastPrimeFactor(n); } } // This code is contributed by Nitin Mittal |
PHP
<?php // PHP program to print the // least prime factors of // numbers less than or equal // to n using modified Sieve // of Eratosthenes function leastPrimeFactor( $n ) { // Create a vector to // store least primes. // Initialize all entries // as 0. $least_prime = array ( $n + 1); for ( $i = 0; $i <= $n ; $i ++) $least_prime [ $i ] = 0; // We need to // print 1 for 1. $least_prime [1] = 1; for ( $i = 2; $i <= $n ; $i ++) { // least_prime[i] == 0 // means it i is prime if ( $least_prime [ $i ] == 0) { // marking the prime // number as its own lpf $least_prime [ $i ] = $i ; // mark it as a divisor // for all its multiples // if not already marked for ( $j = $i * $i ; $j <= $n ; $j += $i ) if ( $least_prime [ $j ] == 0) $least_prime [ $j ] = $i ; } } // print least prime // factor of numbers // till n for ( $i = 1; $i <= $n ; $i ++) echo "Least Prime factor of " . $i . ": " . $least_prime [ $i ] . "\n" ; } // Driver Code $n = 10; leastPrimeFactor( $n ); // This code is contributed // by Sam007 ?> |
Javascript
<script> // javascript program to print the least prime factors // of numbers less than or equal to // n using modified Sieve of Eratosthenes function leastPrimeFactor( n) { // Create a vector to store least primes. // Initialize all entries as 0. let least_prime = Array(n+1).fill(0); // We need to print 1 for 1. least_prime[1] = 1; for (let i = 2; i <= n; i++) { // least_prime[i] == 0 // means it i is prime if (least_prime[i] == 0) { // marking the prime number // as its own lpf least_prime[i] = i; // mark it as a divisor for all its // multiples if not already marked for (let j = i*i; j <= n; j += i) if (least_prime[j] == 0) least_prime[j] = i; } } // print least prime factor of // of numbers till n for (let i = 1; i <= n; i++) document.write( "Least Prime factor of " + i + ": " + least_prime[i] + "<br/>" ); } // Driver program to test above function let n = 10; leastPrimeFactor(n); // This code is contributed by Rajput-Ji </script> |
Least Prime factor of 1: 1 Least Prime factor of 2: 2 Least Prime factor of 3: 3 Least Prime factor of 4: 2 Least Prime factor of 5: 5 Least Prime factor of 6: 2 Least Prime factor of 7: 7 Least Prime factor of 8: 2 Least Prime factor of 9: 3 Least Prime factor of 10: 2
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
References:
1. https://www.w3wiki.net/sieve-of-eratosthenes/
2. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
3. https://oeis.org/wiki/Least_prime_factor_of_n
Exercise:
Can we extend this algorithm or use least_prime[] to find all the prime factors for numbers till n?