计算范围内的最大唯一质因数个数

给定一个数字 N，让我们来找出在范围 [1, N] 内，任意数字最多能拥有的唯一质因数的个数。

示例：

输入：N = 500
输出：4
在 [1, 500] 范围内的任意数字中，
最大质因数个数是 4。
该范围内拥有 4 个质因数的数字是 210 (2 x 3 x 5 x 7)

输入：N = 3
输出：1

输入：N = 5000
输出：5

推荐练习：最大唯一质因数个数 试一试！

方法 1（暴力法）：

我们可以遍历从 1 到 N 的每一个整数，找出每个整数的质因数个数，并找出其中唯一质因数个数最多的那个数字。

方法 2（更优的方法）：

我们可以使用筛法来统计小于 N 的每个数字的质因数数量，然后找出拥有最大计数的最小数字。

下面是这种方法的实现：

在练习平台尝试

C++

// C++ program to find maximum number of prime
// factors for a number in range [1, N]
#include 
using namespace std;

// Return smallest number having maximum
// prime factors.
int maxPrimefactorNum(int N)
{
    // Sieve of eratosthenes method to count
    // number of unique prime factors.
    int arr[N + 1];
    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; 
    }

    // Return maximum element in arr[]
    return *max_element(arr, arr+N);
}

// Driven Program
int main()
{
    int N = 40;
    cout << maxPrimefactorNum(N) << endl;
    return 0;
}

CODEBLOCK_3f2fdbeb


Python3

# Python3 program to find maximum number 
# of prime factors for a number in range [1, N]

# Return smallest number having maximum
# prime factors.
def maxPrimefactorNum(N):

    # Sieve of eratosthenes method to count
    # number of unique prime factors.
    arr = [0] * (N + 1);
    i = 2;
    while (i * i  0):
            for j in range(2 * i, N + 1, i):
                arr[j] += 1;
        i += 1;

        arr[i] = 1; 

    # Return maximum element in arr[]
    return max(arr);

# Driver Code
N = 40;
print(maxPrimefactorNum(N));

# This code is contributed by mits

CODEBLOCK_0e08f5c2


PHP

“`

<?php

// PHP program to find maximum number of prime

// factors for a number in range [1, N]

// Return smallest number having maximum

// prime factors.

function maxPrimefactorNum($N)

{

// Sieve of eratosthenes method to count

// number of unique prime factors.

$arr = array_fill(0, $N + 1, 0);

for ($i = 2; $i * $i <= $N; $i++)

{

if (!$arr[$i])

for ($j = 2 * $i; $j <=