# 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.

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

- 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>` |

**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 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(nlog(n)) **Auxiliary Space:** O(n)**References:**

1. https://www.geeksforgeeks.org/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?

This article is contributed by **Ayush Khanduri**. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. 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.