Given an integer N. The task is to find a number that is smaller than or equal to N and has maximum prime factors. In case there are two or more numbers with the same maximum number of prime factors, find the smallest of all.
Examples:
Input : N = 10
Output : 6
Number of prime factor of:
1 : 0
2 : 1
3 : 1
4 : 1
5 : 1
6 : 2
7 : 1
8 : 1
9 : 1
10 : 2
6 and 10 have maximum (2) prime factor
but 6 is smaller.
Input : N = 40
Output : 30
Method 1 (brute force):
For each integer from 1 to N, find the number of prime factors of each integer and find the smallest number having a maximum number of prime factors.
Method 2 (Better Approach):
Use sieve method to count a number of prime factors of each number less than N. And find the minimum number having maximum count.
Below is the implementation of this approach:
C++
#include<bits/stdc++.h>
using namespace std;
int maxPrimefactorNum(int N)
{
int arr[N + 5];
memset(arr, 0, sizeof(arr));
for (int i = 2; i*i <= N; i++)
{
if (!arr[i])
for (int j = 2*i; j <= N; j+=i)
arr[j]++;
arr[i] = 1;
}
int maxval = 0, maxint = 1;
for (int i = 1; i <= N; i++)
{
if (arr[i] > maxval)
{
maxval = arr[i];
maxint = i;
}
}
return maxint;
}
int main()
{
int N = 40;
cout << maxPrimefactorNum(N) << endl;
return 0;
}
|
Java
import java.util.Arrays;
public class GFG {
static int maxPrimefactorNum(int N) {
int arr[] = new int[N + 5];
Arrays.fill(arr, 0);
for (int i = 2; i * i <= N; i++) {
if (arr[i] == 0) {
for (int j = 2 * i; j <= N; j += i) {
arr[j]++;
}
}
arr[i] = 1;
}
int maxval = 0, maxint = 1;
for (int i = 1; i <= N; i++) {
if (arr[i] > maxval) {
maxval = arr[i];
maxint = i;
}
}
return maxint;
}
public static void main(String[] args) {
int N = 40;
System.out.println(maxPrimefactorNum(N));
}
}
|
Python3
from math import sqrt
def maxPrimefactorNum(N):
arr = [0 for i in range(N + 5)]
for i in range(2, int(sqrt(N)) + 1, 1):
if (arr[i] == 0):
for j in range(2 * i, N + 1, i):
arr[j] += 1
arr[i] = 1
maxval = 0
maxint = 1
for i in range(1, N + 1, 1):
if (arr[i] > maxval):
maxval = arr[i]
maxint = i
return maxint
if __name__ == '__main__':
N = 40
print(maxPrimefactorNum(N))
|
C#
using System;
class GFG
{
static int maxPrimefactorNum(int N)
{
int []arr = new int[N + 5];
for (int i = 2; i * i <= N; i++)
{
if (arr[i] == 0)
{
for (int j = 2 * i; j <= N; j += i)
{
arr[j]++;
}
}
arr[i] = 1;
}
int maxval = 0, maxint = 1;
for (int i = 1; i <= N; i++)
{
if (arr[i] > maxval)
{
maxval = arr[i];
maxint = i;
}
}
return maxint;
}
public static void Main()
{
int N = 40;
Console.WriteLine(maxPrimefactorNum(N));
}
}
|
Javascript
<script>
function maxPrimefactorNum(N) {
var arr = Array.from({length: N + 5}, (_, i) => 0);
for (i = 2; i * i <= N; i++) {
if (arr[i] == 0) {
for (j = 2 * i; j <= N; j += i) {
arr[j]++;
}
}
arr[i] = 1;
}
var maxval = 0, maxvar = 1;
for (i = 1; i <= N; i++) {
if (arr[i] > maxval) {
maxval = arr[i];
maxvar = i;
}
}
return maxvar;
}
var N = 40;
document.write(maxPrimefactorNum(N));
</script>
|
PHP
<?php
function maxPrimefactorNum($N)
{
$arr[$N + 5] = array();
$arr = array_fill(0, $N + 1, NULL);
for ($i = 2; ($i * $i) <= $N; $i++)
{
if (!$arr[$i])
for ($j = 2 * $i; $j <= $N; $j += $i)
$arr[$j]++;
$arr[$i] = 1;
}
$maxval = 0;
$maxint = 1;
for ($i = 1; $i <= $N; $i++)
{
if ($arr[$i] > $maxval)
{
$maxval = $arr[$i];
$maxint = $i;
}
}
return $maxint;
}
$N = 40;
echo maxPrimefactorNum($N), "\n";
?>
|
Time complexity: O(n)
Auxiliary space: O(1)
Method 3 (efficient approach):
Generate all prime numbers before N using Sieve. Now, multiply consecutive prime numbers (starting from the first prime number) one after another until the product is less than N.
Below is the implementation of this approach:
C++
#include<bits/stdc++.h>
using namespace std;
int maxPrimefactorNum(int N)
{
bool arr[N + 5];
memset(arr, true, sizeof(arr));
for (int i = 3; i*i <= N; i += 2)
{
if (arr[i])
for (int j = i*i; j <= N; j+=i)
arr[j] = false;
}
vector<int> prime;
prime.push_back(2);
for(int i = 3; i <= N; i += 2)
if(arr[i])
prime.push_back(i);
int i = 0, ans = 1;
while (ans*prime[i] <= N && i < prime.size())
{
ans *= prime[i];
i++;
}
return ans;
}
int main()
{
int N = 40;
cout << maxPrimefactorNum(N) << endl;
return 0;
}
|
Java
import java.util.Vector;
public class GFG {
static int maxPrimefactorNum(int N) {
boolean arr[] = new boolean[N + 5];
for (int i = 3; i * i <= N; i += 2) {
if (!arr[i]) {
for (int j = i * i; j <= N; j += i) {
arr[j] = true;
}
}
}
Vector<Integer> prime = new Vector<>();
prime.add(prime.size(), 2);
for (int i = 3; i <= N; i += 2) {
if (!arr[i]) {
prime.add(prime.size(), i);
}
}
int i = 0, ans = 1;
while (ans * prime.get(i) <= N && i < prime.size()) {
ans *= prime.get(i);
i++;
}
return ans;
}
public static void main(String[] args) {
int N = 40;
System.out.println(maxPrimefactorNum(N));
}
}
|
Python3
def maxPrimefactorNum(N):
arr = [True] * (N + 5);
i = 3;
while (i * i <= N):
if (arr[i]):
for j in range(i * i, N + 1, i):
arr[j] = False;
i += 2;
prime = [];
prime.append(2);
for i in range(3, N + 1, 2):
if(arr[i]):
prime.append(i);
i = 0;
ans = 1;
while (ans * prime[i] <= N and
i < len(prime)):
ans *= prime[i];
i += 1;
return ans;
N = 40;
print(maxPrimefactorNum(N));
|
C#
using System;
using System.Collections;
class GFG {
static int maxPrimefactorNum(int N)
{
bool []arr = new bool[N + 5];
int i ;
for (i = 3; i * i <= N; i += 2)
{
if (!arr[i])
{
for (int j = i * i; j <= N; j += i)
{
arr[j] = true;
}
}
}
ArrayList prime = new ArrayList();
prime.Add(2);
for (i = 3; i <= N; i += 2)
{
if (!arr[i])
{
prime.Add(i);
}
}
int ans = 1;
i = 0;
while (ans * (int)prime[i] <= N && i < prime.Count)
{
ans *= (int)prime[i];
i++;
}
return ans;
}
public static void Main()
{
int N = 40;
Console.Write(maxPrimefactorNum(N));
}
}
|
Javascript
<script>
function maxPrimefactorNum(N)
{
let arr = new Array(N + 5);
arr.fill(false);
let i ;
for (i = 3; i * i <= N; i += 2)
{
if (!arr[i])
{
for (let j = i * i; j <= N; j += i)
{
arr[j] = true;
}
}
}
let prime = [];
prime.push(2);
for (i = 3; i <= N; i += 2)
{
if (!arr[i])
{
prime.push(i);
}
}
let ans = 1;
i = 0;
while (ans * prime[i] <= N && i < prime.length)
{
ans *= prime[i];
i++;
}
return ans;
}
let N = 40;
document.write(maxPrimefactorNum(N));
</script>
|
PHP
<?php
function maxPrimefactorNum($N)
{
$arr = array_fill(0, $N + 5, true);
for ($i = 3; $i * $i <= $N; $i += 2)
{
if ($arr[$i])
for ($j = $i * $i; $j <= $N; $j += $i)
$arr[$j] = false;
}
$prime = array();
array_push($prime, 2);
for($i = 3; $i <= $N; $i += 2)
if($arr[$i])
array_push($prime, $i);
$i = 0;
$ans = 1;
while ($ans * $prime[$i] <= $N &&
$i < count($prime))
{
$ans *= $prime[$i];
$i++;
}
return $ans;
}
$N = 40;
print(maxPrimefactorNum($N));
?>
|
Time complexity: O(nsqrtn)
Auxiliary space: O(n)
Prime Factorization Method:
Approach:
In this approach, we factorize all numbers from 1 to N and count the number of prime factors for each number. We can use a prime factorization algorithm like trial division or Pollard’s rho algorithm.
- Define a function prime_factors_trial_division(n) that takes an integer n as input and returns a list of prime factors of n using the trial division method. The trial division method involves dividing n by each integer from 2 to the square root of n, and adding each integer that divides n without a remainder to the list of factors. If no integer from 2 to the square root of n divides n without a remainder, then n itself is a prime factor and is added to the list of factors.
- Define a function count_prime_factors(n) that takes an integer n as input and returns the count of distinct prime factors of n. The function first calls the prime_factors_trial_division(n) function to get the list of prime factors, and then converts the list to a set to remove duplicates. The length of the set is then returned as the count of distinct prime factors.
- Define a function max_prime_factors_prime_factorization(n) that takes an integer n as input and returns the number between 1 and n that has the maximum number of distinct prime factors. The function iterates through all integers from 1 to n, calls the count_prime_factors(n) function to get the count of distinct prime factors for each integer, and updates the max_count and max_num variables if the count for the current integer is greater than the current maximum count. The function returns the max_num variable as the output.
- Use the max_prime_factors_prime_factorization(n) function to find the number between 1 and n that has the maximum number of distinct prime factors. Print the result as the output.
C++
#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector<int> prime_factors_trial_division(int n)
{
vector<int> factors;
int i = 2;
while (i * i <= n) {
if (n % i == 0) {
factors.push_back(i);
n /= i;
}
else {
i++;
}
}
if (n > 1) {
factors.push_back(
n);
}
return factors;
}
int count_prime_factors(int n)
{
vector<int> factors = prime_factors_trial_division(n);
set<int> unique_factors(factors.begin(), factors.end());
int count = unique_factors.size();
return count;
}
int max_prime_factors_prime_factorization(int n)
{
int max_count = 0;
int max_num = 0;
for (int i = 1; i <= n; i++) {
int count = count_prime_factors(
i);
if (count > max_count) {
max_count = count;
max_num = i;
}
}
return max_num;
}
int main()
{
int n = 10;
cout << "Input : N = " << n << endl;
cout << "Number of prime factors of:" << endl;
for (int i = 1; i <= n; i++) {
vector<int> factors
= prime_factors_trial_division(i);
int count = count_prime_factors(i);
cout << i << " : " << count << endl;
}
int max_num = max_prime_factors_prime_factorization(n);
cout << max_num
<< " has the maximum number of prime factors "
"among all numbers from 1 to "
<< n << endl;
n = 40;
cout << "Input : N = " << n << endl;
max_num = max_prime_factors_prime_factorization(n);
cout << max_num
<< " has the maximum number of prime factors "
"among all numbers from 1 to "
<< n << endl;
return 0;
}
|
Python3
def prime_factors_trial_division(n):
factors = []
i = 2
while i * i <= n:
if n % i == 0:
factors.append(i)
n //= i
else:
i += 1
if n > 1:
factors.append(n)
return factors
def count_prime_factors(n):
factors = prime_factors_trial_division(n)
count = len(set(factors))
return count
def max_prime_factors_prime_factorization(n):
max_count = 0
max_num = 0
for i in range(1, n+1):
count = count_prime_factors(i)
if count > max_count:
max_count = count
max_num = i
return max_num
n = 10
print("Input : N =", n)
print("Number of prime factors of:")
for i in range(1, n+1):
factors = prime_factors_trial_division(i)
count = len(set(factors))
print(i, ":", count)
max_num = max_prime_factors_prime_factorization(n)
print(max_num, "has maximum number of prime factors among all numbers from 1 to", n)
n = 40
print("Input : N =", n)
max_num = max_prime_factors_prime_factorization(n)
print(max_num, "has maximum number of prime factors among all numbers from 1 to", n)
|
Javascript
function prime_factors_trial_division(n) {
const factors = [];
let i = 2;
while (i * i <= n) {
if (n % i === 0) {
factors.push(i);
n /= i;
} else {
i++;
}
}
if (n > 1) {
factors.push(n);
}
return factors;
}
function count_prime_factors(n) {
const factors = prime_factors_trial_division(n);
const unique_factors = [...new Set(factors)];
return unique_factors.length;
}
function max_prime_factors_prime_factorization(n) {
let max_count = 0;
let max_num = 0;
for (let i = 1; i <= n; i++) {
const count = count_prime_factors(i);
if (count > max_count) {
max_count = count;
max_num = i;
}
}
return max_num;
}
const n1 = 10;
console.log("Input : N =", n1);
console.log("Number of prime factors of:");
for (let i = 1; i <= n1; i++) {
const factors = prime_factors_trial_division(i);
const count = [...new Set(factors)].length;
console.log(i, ":", count);
}
const maxNum1 = max_prime_factors_prime_factorization(n1);
console.log(maxNum1, "has maximum number of prime factors among all numbers from 1 to", n1);
const n2 = 40;
console.log("Input : N =", n2);
const maxNum2 = max_prime_factors_prime_factorization(n2);
console.log(maxNum2, "has maximum number of prime factors among all numbers from 1 to", n2);
|
Output
Input : N = 10
Number of prime factors of:
1 : 0
2 : 1
3 : 1
4 : 1
5 : 1
6 : 2
7 : 1
8 : 1
9 : 1
10 : 2
6 has maximum number of prime factors among all numbers from 1 to 10
Input : N = 40
30 has maximum number of prime factors among all numbers from 1 to 40
Time Complexity: O(N log log N)
Space Complexity: O(1)
This article is contributed byAnuj Chauhan. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek 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.
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 zambiatek!
