Рубрики

Количество различных простых факторов первых n натуральных чисел

Учитывая число N, найдите число различных простых факторов для всех чисел в диапазоне [1, N].

Примеры :

Input : N = 3
Output :  0 1 1
Number of distinct Prime Factors of 1 is 0
Number of distinct Prime Factors of 2 is 1
Number of distinct Prime Factors of 3 is 1

Input : 6
Output : 0 1 1 1 1 2
Number of distinct Prime Factors of 1 is 0
Number of distinct Prime Factors of 2 is 1
Number of distinct Prime Factors of 3 is 1
Number of distinct Prime Factors of 4 is 1
Number of distinct Prime Factors of 5 is 1
Number of distinct Prime Factors of 6 is 2
2, 3 and 5 are themselves prime. The only prime 
factor of 4 is 2.The two prime factors of 6 are 
2 and 3.

Идея основана на Сите Эратхофена . Всякий раз, когда мы отмечаем число как простое число, мы также увеличиваем число простых факторов в его множителях.

C ++

// C ++ программа для поиска числа различных простых факторов
// для всего числа в диапазоне [1, N]
#include <bits/stdc++.h>

using namespace std;

  

void printDistinctPFs(int n)

{

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

    long long factorCount[n + 1];

  

    // истина, если индекс 'i' простое число

    bool prime[n + 1];

  

    // инициализация числа факторов до 0 и

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

        factorCount[i] = 0;

        prime[i] = true// Используется в сите

    }

  

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

   

        // условие работает только тогда, когда 'i' простое,

        // следовательно, для факторов всех простых чисел,

        // первичный статус изменен на ложный

        if (prime[i] == true) { 

              

            // Число простое

            factorCount[i] = 1; 

              

            // номер фактора простого числа равен 1

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

  

                // увеличиваем коэффициент factorCount all

                // факторы меня

                factorCount[j]++; 

  

                // и изменение основного статуса на false

                prime[j] = false

            }

        }

    }

  

    // Печать результата

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

        cout << factorCount[i] << " ";

}

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

int main()

{

    int n = 20; // ввод

    printDistinctPFs(n); 

    return 0;

}

Джава

// Java программа для поиска номера
// различных простых факторов
// для всего числа в диапазоне [1, N]

import java.io.*;

  

class GFG 

{

static void printDistinctPFs(int n)

{

    // массив для хранения номера

    // различных простых чисел

    long factorCount[] = new long[n + 1];

  

    // истина, если индекс 'i' простое число

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

  

    // инициализация числа

    // факторов до 0 и

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

    {

        factorCount[i] = 0;

        prime[i] = true; // Используется в сите

    }

  

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

    {

  

        // условие работает только когда

        // 'i' простое, следовательно, для

        // факторы всех простых чисел,

        // первичный статус изменен на ложный

        if (prime[i] == true

        

              

            // Число простое

            factorCount[i] = 1

              

            // номер фактора

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

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

            {

  

                // увеличиваем коэффициент множителя

                // все факторы я

                factorCount[j]++; 

  

                // и меняем простое число

                // статус в ложь

                prime[j] = false

            }

        }

    }

  

    // Печать результата

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

    System.out.print( factorCount[i] + " ");

}

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

public static void main (String[] args)

{

    int n = 20; // ввод

    printDistinctPFs(n);

}
}

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

python3

# Python3 программа для поиска
# число различных простых
# факторы для всего числа
# в диапазоне [1, N]

def printDistinctPFs(n):

      

    # массив для хранения

    # число различных простых чисел

    factorCount = [];

  

    # true если индекс

    # 'i' - простое число

    prime = [];

  

    # инициализация номера

    Количество факторов до 0 и

    for i in range(n + 1): 

        factorCount.append(0);

        prime.append(1); 

        # Используется в сите

  

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

          

        # условие работает только

        # когда «я» простое,

        # следовательно для факторов

        # все простое число,

        # основной статус

        # изменено на ложное

        if (prime[i] == 1): 

              

            Номер простое

            factorCount[i] = 1

              

            № номер фактора

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

            j = i * 2;

            while(j <= n): 

                  

                # увеличивающий коэффициентCount

                # все факторы я

                factorCount[j] = factorCount[j] + 1

  

                # и изменение простого числа

                # статус в ложь

                prime[j] = 0;

                j = j + i;

  

    # Результат печати

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

        print(factorCount[i] ,

                   end = " ");

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

n = 20;

  
# вход
printDistinctPFs(n); 

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

C #

// C # программа для поиска номера
// различных простых факторов
// для всего числа в диапазоне [1, N]

using System;

  

class GFG 

{

static void printDistinctPFs(int n)

{

    // массив для хранения номера

    // различных простых чисел

    long []factorCount = new long[n + 1];

  

    // истина, если индекс 'i' простое число

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

  

    // инициализация числа

    // факторов до 0 и

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

    {

        factorCount[i] = 0;

        prime[i] = true; // Используется в сите

    }

  

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

    {

  

        // условие работает только

        // когда 'i' простое число,

        // следовательно, для факторов

        // все простое число,

        // основной статус изменен

        // в ложь

        if (prime[i] == true

        

              

            // Число простое

            factorCount[i] = 1; 

              

            // номер фактора

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

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

            {

  

                // увеличиваем коэффициент множителя

                // все факторы я

                factorCount[j]++; 

  

                // и меняем простое число

                // статус в ложь

                prime[j] = false

            }

        }

    }

  

    // Печать результата

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

    Console.Write(factorCount[i] + " ");

}

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

public static void Main ()

{

    int n = 20; // ввод

    printDistinctPFs(n);

}
}

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

PHP

<?php
// PHP программа для поиска номера
// различных простых факторов
// для всего числа в диапазоне [1, N]

function printDistinctPFs($n)

{

    // массив для хранения

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

    $factorCount = array();

  

    // true если индекс

    // 'i' - простое число

    $prime = array();

  

    // инициализация числа

    // факторов до 0 и

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

    {

        $factorCount[$i] = 0;

        $prime[$i] = true; // Используется в сите

    }

  

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

    {

  

        // условие работает только

        // когда 'i' простое число,

        // следовательно, для факторов

        // все простое число,

        // первичный статус

        // изменено на false

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

        

              

            // Число простое

            $factorCount[$i] = 1; 

              

            // номер фактора

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

            for ($j = $i * 2; 

                 $j <= $n; $j += $i

            {

  

                // увеличиваем коэффициент множителя

                // все факторы я

                $factorCount[$j]++; 

  

                // и меняем простое число

                // статус в ложь

                $prime[$j] = false; 

            }

        }

    }

  

    // Печать результата

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

        echo $factorCount[$i] , " ";

}

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

$n = 20; // ввод

printDistinctPFs($n); 

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

Выход :

0 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 2 1 2

Это наиболее эффективный способ вычисления числа простых факторов для чисел в [1, N]. Здесь тип данных n, factorCount может быть изменен для решения проблем с огромными ограничениями.

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

Количество различных простых факторов первых n натуральных чисел

0.00 (0%) 0 votes