Рубрики

Подсчет делителей n в O (n ^ 1/3)

Учитывая число n, посчитайте все его различные делители.

Примеры:

Input : 18
Output : 6
Divisors of 18 are 1, 2, 3, 6, 9 and 18.

Input : 100
Output : 9
Divisors of 100 are 1, 2, 4, 5, 10, 20,
25, 50 and 100

Наивным решением было бы перебрать все числа от 1 до sqrt (n), проверяя, делит ли это число n и увеличивая число делителей. Этот подход занимает O (sqrt (n)) время.

C ++

// C реализация метода Naive для подсчета всех
// делители
#include <bits/stdc++.h>

using namespace std;

  
// функция для подсчета делителей

int countDivisors(int n)

{

    int cnt = 0;

    for (int i = 1; i <= sqrt(n); i++) {

        if (n % i == 0) {

            // Если делители равны,

            // считать только один

            if (n / i == i)

                cnt++;

  

            else // В противном случае считать оба

                cnt = cnt + 2;

        }

    }

    return cnt;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    printf("Total distinct divisors of 100 are : %d",

           countDivisors(100));

    return 0;

}

Джава

// реализация Java наивного метода
// посчитать все делители

import java.io.*;

import java.math.*;

  

class GFG {

  

    // функция для подсчета делителей

    static int countDivisors(int n)

    {

        int cnt = 0;

        for (int i = 1; i <= Math.sqrt(n); i++)

        {

            if (n % i == 0) {

                // Если делители равны,

                // считать только один

                if (n / i == i)

                    cnt++;

  

                else // В противном случае считать оба

                    cnt = cnt + 2;

            }

        }

        return cnt;

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[])

    {

        System.out.println("Total distinct "

                  + "divisors of 100 are : "  

                       + countDivisors(100));

    }

}

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Python3 реализация метода Naive
# считать все делители

  

import math

  
# функция для подсчета делителей

def countDivisors(n) :

    cnt = 0

    for i in range(1, (int)(math.sqrt(n)) + 1) :

        if (n % i == 0) :

              

            # Если делители равны,

            # считать только один

            if (n / i == i) :

                cnt = cnt + 1

            else : # В противном случае считать оба

                cnt = cnt + 2

                  

    return cnt

      
# Программа драйвера для проверки вышеуказанной функции * /

  

print("Total distinct divisors of 100 are : ",

      countDivisors(100))

  
# Этот код предоставлен Никитой Тивари.

C #

// C # реализация Наивного метода
// посчитать все делители

using System;

  

class GFG {

  

    // функция для подсчета делителей

    static int countDivisors(int n)

    {

        int cnt = 0;

        for (int i = 1; i <= Math.Sqrt(n);

                                      i++)

        {

            if (n % i == 0) {

                  

                // Если делители равны,

                // считать только один

                if (n / i == i)

                    cnt++;

  

                // В противном случае считать оба

                else

                    cnt = cnt + 2;

            }

        }

          

        return cnt;

    }

  

    // Драйвер программы

    public static void Main()

    {

        Console.WriteLine("Total distinct"

               + " divisors of 100 are : "

                    + countDivisors(100));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP реализация Naive
// метод подсчета всех делителей

  
// функция для подсчета делителей

  

function countDivisors($n)

{

    $cnt = 0;

    for ($i = 1; $i <= sqrt($n); $i++)

    {

        if ($n % $i == 0)

        {

            // Если делители равны,

            // считать только один

            if ($n / $i == $i)

            $cnt++;

  

            // В противном случае считать оба

            else 

                $cnt = $cnt + 2;

        }

    }

    return $cnt;

}

  
// Код драйвера

echo "Total distinct divisors of 100 are : ",

        countDivisors(100);

  
// Этот код предоставлен Ajit
?>


Выход :

Total distinct divisors of 100 are : 9

Оптимизированное решение (O (n ^ 1/3))

  1. Разбейте число n на два числа x и y, так что n = x * y, где x содержит только простые множители в диапазоне 2 <= x <= n (1/3), а y имеет дело с более высокими простыми множителями, большими, чем n (1/3 )
  2. Подсчитайте суммарные факторы x, используя метод наивного пробного деления. Пусть это количество будет F (x).
  3. Подсчитайте суммарные факторы у, используя следующие три случая. Пусть это количество будет F (y).
    • Если y — простое число, то коэффициентами будут 1 и сам y. Это означает, что F (y) = 2.
    • Если y является квадратом простого числа, то коэффициентами будут 1, sqrt (y) и сам y. Это означает, что F (y) = 3.
    • Если у — произведение двух различных простых чисел, то факторы будут равны 1, как простым числам, так и самому числу у. Это означает, что F (y) = 4.
  4. Так как F (x * y) является мультипликативной функцией и gcd (x, y) = 1, это означает, что F (x * y) = F (x) * F (y), что дает количество полных различных делителей n ,

Обратите внимание, что у нас есть только эти три случая для вычисления факторов y, поскольку может быть максимум два простых множителя y. Если бы в нем было более двух простых факторов, один из них, несомненно, был бы меньше, чем n (1/3) , и, следовательно, он был бы включен в x, а не в y.

C ++

// C ++ программа для подсчета различных делителей
// данного числа n
#include <bits/stdc++.h>

using namespace std;

  

void SieveOfEratosthenes(int n, bool prime[],

                         bool primesquare[], int a[])

{

    // Создаем логический массив "prime [0..n]" и

    // инициализируем все записи как true. Ценность

    // в простом [i] будет, наконец, ложным, если я

    // Не простое число, иначе верно.

    for (int i = 2; i <= n; i++)

        prime[i] = true;

  

    // Создаем логический массив "primesquare [0..n * n + 1]"

    // и инициализируем все записи как ложные. Ценность

    // в squareprime [i] будет наконец истина, если я

    // квадрат простого числа, иначе ложь.

    for (int i = 0; i <= (n * n + 1); i++)

        primesquare[i] = false;

  

    // 1 не простое число

    prime[1] = false;

  

    for (int p = 2; p * p <= n; p++) {

        // Если штрих [p] не изменился, то

        // это простое число

        if (prime[p] == true) {

            // Обновить все кратные р

            for (int i = p * 2; i <= n; i += p)

                prime[i] = false;

        }

    }

  

    int j = 0;

    for (int p = 2; p <= n; p++) {

        if (prime[p]) {

            // Сохранение простых чисел в массиве

            a[j] = p;

  

            // Обновить значение в primesquare [p * p],

            // если p простое.

            primesquare[p * p] = true;

            j++;

        }

    }

}

  
// Функция для подсчета делителей

int countDivisors(int n)

{

    // Если число равно 1, то оно будет иметь только 1

    // как фактор. Итак, суммарные факторы будут 1.

    if (n == 1)

        return 1;

  

    bool prime[n + 1], primesquare[n * n + 1];

  

    int a[n]; // для хранения простых чисел до n

  

    // Вызов SieveOfEratosthenes для хранения простого

    // факторы n и хранить квадрат простого числа

    // факторы п

    SieveOfEratosthenes(n, prime, primesquare, a);

  

    // ANS будет содержать общее количество различных

    // делители

    int ans = 1;

  

    // Цикл для подсчета факторов n

    for (int i = 0;; i++) {

        // a [i] не меньше, чем корень куба n

        if (a[i] * a[i] * a[i] > n)

            break;

  

        // Расчет мощности a [i] в n.

        int cnt = 1; // cnt - степень простого числа a [i] в n.

        while (n % a[i] == 0) // если a [i] является фактором n

        {

            n = n / a[i];

            cnt = cnt + 1; // увеличение мощности

        }

  

        // Расчет количества делителей

        // Если n = a ^ p * b ^ q, то суммарные делители n

        // есть (p + 1) * (q + 1)

        ans = ans * cnt;

    }

  

    // если a [i] больше кубического корня из n

  

    // Первый случай

    if (prime[n])

        ans = ans * 2;

  

    // Второй случай

    else if (primesquare[n])

        ans = ans * 3;

  

    // Третий случай

    else if (n != 1)

        ans = ans * 4;

  

    return ans; // Итого делителей

}

  
// Программа для водителя

int main()

{

    cout << "Total distinct divisors of 100 are : "

         << countDivisors(100) << endl;

    return 0;

}

Джава

// JAVA программа для подсчета
// делители заданного числа n

import java.io.*;

  

class GFG {

  

    static void SieveOfEratosthenes(int n, boolean prime[],

                                    boolean primesquare[], int a[])

    {

        // Создаем логический массив "prime [0..n]" и

        // инициализируем все записи как true. Ценность

        // в простом [i] будет, наконец, ложным, если я

        // Не простое число, иначе верно.

        for (int i = 2; i <= n; i++)

            prime[i] = true;

  

        / * Создать логический массив "primesquare [0..n * n + 1]"

         и инициализировать все записи как ложные.

         Значение в squareprime [i] будет, наконец,

         быть правдой, если я квадрат простого числа,

         иначе ложь. * /

        for (int i = 0; i < ((n * n) + 1); i++)

            primesquare[i] = false;

  

        // 1 не простое число

        prime[1] = false;

  

        for (int p = 2; p * p <= n; p++) {

            // Если простое число [p] не изменилось,

            // тогда это простое число

            if (prime[p] == true) {

                // Обновить все кратные р

                for (int i = p * 2; i <= n; i += p)

                    prime[i] = false;

            }

        }

  

        int j = 0;

        for (int p = 2; p <= n; p++) {

            if (prime[p]) {

                // Сохранение простых чисел в массиве

                a[j] = p;

  

                // Обновить значение в

                // primesquare [p * p],

                // если p простое.

                primesquare[p * p] = true;

                j++;

            }

        }

    }

  

    // Функция для подсчета делителей

    static int countDivisors(int n)

    {

        // Если число равно 1, то оно будет

        // иметь только 1 как фактор. Так,

        // суммарные факторы будут 1.

        if (n == 1)

            return 1;

  

        boolean prime[] = new boolean[n + 1];

        boolean primesquare[] = new boolean[(n * n) + 1];

  

        // для хранения простых чисел до n

        int a[] = new int[n];

  

        // Вызов SieveOfEratosthenes для

        // сохраняем простые множители n и to

        // сохраняем квадрат простых множителей n

        SieveOfEratosthenes(n, prime, primesquare, a);

  

        // ANS будет содержать общее количество

        // различных делителей

        int ans = 1;

  

        // Цикл для подсчета факторов n

        for (int i = 0;; i++) {

            // a [i] не меньше, чем корень куба n

            if (a[i] * a[i] * a[i] > n)

                break;

  

            // Расчет мощности a [i] в n.

            // cnt - степень простого числа a [i] в n.

            int cnt = 1;

  

            // если a [i] является фактором n

            while (n % a[i] == 0) {

                n = n / a[i];

  

                // увеличение мощности

                cnt = cnt + 1;

            }

  

            // Расчет количества делителей

            // Если n = a ^ p * b ^ q, то всего

            // делителями n являются (p + 1) * (q + 1)

            ans = ans * cnt;

        }

  

        // если a [i] больше корня куба

        // из n

  

        // Первый случай

        if (prime[n])

            ans = ans * 2;

  

        // Второй случай

        else if (primesquare[n])

            ans = ans * 3;

  

        // Третий случай

        else if (n != 1)

            ans = ans * 4;

  

        return ans; // Итого делителей

    }

  

    // Программа для водителя

    public static void main(String args[])

    {

        System.out.println("Total distinct divisors"

                           + " of 100 are : " + countDivisors(100));

    }

}

  
/ * Этот код предоставлен Никитой Тивари * /

python3

# Python3 программа для подсчета
# делителей заданного числа n

  

def SieveOfEratosthenes(n, prime,primesquare, a):

    # Создайте логический массив "prime [0..n]"

    # и инициализировать все записи как

    # правда. Значение в простом [i] будет, наконец,

    # быть ложным, если я не простое число, иначе верно.

    for i in range(2,n+1):

        prime[i] = True

  

    # Создайте логический массив "primesquare [0..n * n + 1]"

    # и инициализировать все записи как ложные.

    # Значение в squareprime [i] будет наконец

    # true, если я квадрат простого числа, иначе false.

    for i in range((n * n + 1)+1):

        primesquare[i] = False

  

    # 1 не простое число

    prime[1] = False

  

    p = 2

    while(p * p <= n):

        # Если простое число [p] не изменилось,

        # тогда это простое

        if (prime[p] == True):

            # Обновить все кратные р

            i = p * 2 

            while(i <= n):

                prime[i] = False

                i += p

        p+=1

      

  

    j = 0

    for p in range(2,n+1): 

        if (prime[p]==True): 

            # Хранение простых чисел в массиве

            a[j] = p

  

            # Обновить значение в primesquare [p * p],

            # если p простое число.

            primesquare[p * p] = True

            j+=1

  
# Функция для подсчета делителей

def countDivisors(n):

    # Если число равно 1, то оно будет

    # есть только 1 как фактор. Так,

    # Всего факторов будет 1.

    if (n == 1):

        return 1

  

    prime = [False]*(n + 2)

    primesquare = [False]*(n * n + 2)

      

    # для хранения простых чисел до n

    a = [0]*n

  

    # Вызов SieveOfEratosthenes для

    # хранить простые множители n и to

    # хранить площадь простых множителей n

    SieveOfEratosthenes(n, prime, primesquare, a)

  

    # ans будет содержать всего

    количество различных делителей

    ans = 1

  

    # Цикл для подсчета факторов n

    i=0

    while(1): 

        # a [i] не меньше кубического корня n

        if(a[i] * a[i] * a[i] > n):

            break

  

        # Расчет мощности [i] в n.

        cnt = 1 # cnt - это сила

                # премьер а [я] в п.

        while (n % a[i] == 0): # если a [i] является фактором n

            n = n / a[i]

            cnt = cnt + 1 # увеличение мощности

  

        # Расчет количества делителей

        # Если n = a ^ p * b ^ q, то всего

        # делителями n являются (p + 1) * (q + 1)

        ans = ans * cnt

        i+=1

  

    # если a [i] больше чем

    # кубический корень из n

      

    n=int(n)

    # Первый случай

    if (prime[n]==True):

        ans = ans * 2

  

    # Второй случай

    elif (primesquare[n]==True):

        ans = ans * 3

  

    Третий случай

    elif (n != 1):

        ans = ans * 4

  

    return ans # Всего делителей

  
Код водителя

if __name__=='__main__':

    print("Total distinct divisors of 100 are :",countDivisors(100))

  
# Этот код добавлен
# по митсам

C #

// C # программа для подсчета
// делители заданного числа n

using System;

  

class GFG {

  

    static void SieveOfEratosthenes(int n, bool[] prime,

                                    bool[] primesquare, int[] a)

    {

  

        // Создаем логический массив "prime [0..n]" и

        // инициализируем все записи как true. Ценность

        // в простом [i] будет, наконец, ложным, если я

        // Не простое число, иначе верно.

        for (int i = 2; i <= n; i++)

            prime[i] = true;

  

        / * Создать логический массив "primesquare [0..n * n + 1]"

        и инициализировать все записи как ложные.

        Значение в squareprime [i] будет, наконец,

        быть правдой, если я квадрат простого числа,

        иначе ложь. * /

        for (int i = 0; i < ((n * n) + 1); i++)

            primesquare[i] = false;

  

        // 1 не простое число

        prime[1] = false;

  

        for (int p = 2; p * p <= n; p++) {

  

            // Если простое число [p] не изменилось,

            // тогда это простое число

            if (prime[p] == true) {

  

                // Обновить все кратные р

                for (int i = p * 2; i <= n; i += p)

                    prime[i] = false;

            }

        }

  

        int j = 0;

        for (int p = 2; p <= n; p++) {

            if (prime[p]) {

  

                // Сохранение простых чисел в массиве

                a[j] = p;

  

                // Обновить значение в

                // primesquare [p * p],

                // если p простое.

                primesquare[p * p] = true;

                j++;

            }

        }

    }

  

    // Функция для подсчета делителей

    static int countDivisors(int n)

    {

  

        // Если число равно 1, то оно будет

        // иметь только 1 как фактор. Так,

        // суммарные факторы будут 1.

        if (n == 1)

            return 1;

  

        bool[] prime = new bool[n + 1];

        bool[] primesquare = new bool[(n * n) + 1];

  

        // для хранения простых чисел до n

        int[] a = new int[n];

  

        // Вызов SieveOfEratosthenes для

        // сохраняем простые множители n и to

        // сохраняем квадрат простых множителей n

        SieveOfEratosthenes(n, prime, primesquare, a);

  

        // ANS будет содержать общее количество

        // различных делителей

        int ans = 1;

  

        // Цикл для подсчета факторов n

        for (int i = 0;; i++) {

  

            // a [i] не меньше, чем корень куба n

            if (a[i] * a[i] * a[i] > n)

                break;

  

            // Расчет мощности a [i] в n.

            // cnt - степень простого числа a [i] в n.

            int cnt = 1;

  

            // если a [i] является фактором n

            while (n % a[i] == 0) {

                n = n / a[i];

  

                // увеличение мощности

                cnt = cnt + 1;

            }

  

            // Расчет количества делителей

            // Если n = a ^ p * b ^ q, то всего

            // делителями n являются (p + 1) * (q + 1)

            ans = ans * cnt;

        }

  

        // если a [i] больше корня куба

        // из n

  

        // Первый случай

        if (prime[n])

            ans = ans * 2;

  

        // Второй случай

        else if (primesquare[n])

            ans = ans * 3;

  

        // Третий случай

        else if (n != 1)

            ans = ans * 4;

  

        return ans; // Итого делителей

    }

  

    // Программа для водителя

    public static void Main()

    {

        Console.Write("Total distinct divisors"

                      + " of 100 are : " + countDivisors(100));

    }

}

  
// Этот код предоставлен parashar.

PHP

<?php 
// PHP программа для подсчета
// делители заданного числа n

  

function SieveOfEratosthenes($n, &$prime,

                             &$primesquare, &$a)

{

    // Создаем логический массив "prime [0..n]"

    // и инициализируем все записи как

    // правда. Значение в простом [i] будет, наконец,

    // быть ложным, если я не простое число, иначе верно.

    for ($i = 2; $i <= $n; $i++)

        $prime[$i] = true;

  

    // Создаем логический массив "primesquare [0..n * n + 1]"

    // и инициализируем все записи как ложные.

    // Значение в squareprime [i] будет наконец

    // истина, если я - квадрат простого числа, иначе ложь.

    for ($i = 0; $i <= ($n * $n + 1); $i++)

        $primesquare[$i] = false;

  

    // 1 не простое число

    $prime[1] = false;

  

    for ($p = 2; $p * $p <= $n; $p++)

    {

        // Если простое число [p] не изменилось,

        // тогда это простое число

        if ($prime[$p] == true)

        {

            // Обновить все кратные р

            for ($i = $p * 2; 

                 $i <= $n; $i += $p)

                $prime[$i] = false;

        }

    }

  

    $j = 0;

    for ($p = 2; $p <= $n; $p++) 

    {

        if ($prime[$p]) 

        {

            // Сохранение простых чисел в массиве

            $a[$j] = $p;

  

            // Обновить значение в primesquare [p * p],

            // если p простое.

            $primesquare[$p * $p] = true;

            $j++;

        }

    }

}

  
// Функция для подсчета делителей

function countDivisors($n)

{

    // Если число равно 1, то оно будет

    // иметь только 1 как фактор. Так,

    // суммарные факторы будут 1.

    if ($n == 1)

        return 1;

  

    $prime = array_fill(false, $n + 1, NULL);

    $primesquare = array_fill(false, 

                          $n * $n + 1, NULL);

      

    // для хранения простых чисел до n

    $a = array_fill(0, $n, NULL);

   

    // Вызов SieveOfEratosthenes для

    // сохраняем простые множители n и to

    // сохраняем квадрат простых множителей n

    SieveOfEratosthenes($n, $prime

                        $primesquare, $a);

  

    // ANS будет содержать всего

    // количество различных делителей

    $ans = 1;

  

    // Цикл для подсчета факторов n

    for ($i = 0;; $i++) 

    {

        // a [i] не меньше, чем корень куба n

        if ($a[$i] * $a[$i] * $a[$i] > $n)

            break;

  

        // Расчет мощности a [i] в n.

        $cnt = 1; // cnt это сила

                  // простое число [i] в n.

        while ($n % $a[$i] == 0) // если [i] является

                                 // коэффициент n

        {

            $n = $n / $a[$i];

            $cnt = $cnt + 1; // увеличение мощности

        }

  

        // Расчет количества делителей

        // Если n = a ^ p * b ^ q, то всего

        // делителями n являются (p + 1) * (q + 1)

        $ans = $ans * $cnt;

    }

  

    // если a [i] больше чем

    // кубический корень из n

  

    // Первый случай

    if ($prime[$n])

        $ans = $ans * 2;

  

    // Второй случай

    else if ($primesquare[$n])

        $ans = $ans * 3;

  

    // Третий случай

    else if ($n != 1)

        $ans = $ans * 4;

  

    return $ans; // Итого делителей

}

  
// Код драйвера

echo "Total distinct divisors of 100 are : ".

                    countDivisors(100). "\n";

  
// Этот код добавлен
// ChitraNayal
?>


Выход :

Total distinct divisors of 100 are : 9

Сложность времени: O (n 1/3 )

Эта статья предоставлена Рахул Агравал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчет делителей n в O (n ^ 1/3)

0.00 (0%) 0 votes