Фраза «подсчет различных простых множителей числа» относится к нахождению количества уникальных простых множителей данного числа. Вот несколько способов выполнить эту задачу, а также примеры кода:

Метод 1: перебор
Этот метод включает в себя перебор всех чисел до заданного и проверку, являются ли они простыми множителями.

def distinct_prime_factors_count_brute_force(n):
    factors = set()
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.add(i)
    if n > 1:
        factors.add(n)
    return len(factors)

Метод 2: Пробное разделение
Этот метод представляет собой оптимизированную версию метода грубой силы, при котором нам нужно проверять только простые числа в качестве потенциальных факторов.

def distinct_prime_factors_count_trial_division(n):
    factors = set()
    d = 2
    while d * d <= n:
        if n % d == 0:
            factors.add(d)
            while n % d == 0:
                n //= d
        d += 1
    if n > 1:
        factors.add(n)
    return len(factors)

Метод 3: Решето Эратосфена
Этот метод включает в себя использование алгоритма Решето Эратосфена для генерации всех простых чисел до заданного числа, а затем проверку того, какие из этих простых чисел являются множителями.

def distinct_prime_factors_count_sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    factors = set()
    for p in range(2, n + 1):
        if sieve[p]:
            if n % p == 0:
                factors.add(p)
                while n % p == 0:
                    n //= p
            for i in range(p * p, n + 1, p):
                sieve[i] = False
    if n > 1:
        factors.add(n)
    return len(factors)