Рубрики

Наименьший простой множитель чисел до n

Для числа n выведите наименьшие простые множители из всех чисел от 1 до n. Наименьший простой множитель целого числа n — это наименьшее простое число, которое делит число. Наименьший простой множитель среди всех четных чисел равен 2. Простое число — это его собственный наименьший простой множитель (а также его собственный наибольший простой множитель).

Примечание: нам нужно напечатать 1 для 1.

Пример :

Input : 6
Output : Least Prime factor of 1: 1
         Least Prime factor of 2: 2
         Least Prime factor of 3: 3
         Least Prime factor of 4: 2
         Least Prime factor of 5: 5
         Least Prime factor of 6: 2

Мы можем использовать разновидность сита Эратосфена для решения вышеуказанной проблемы.

    Алгоритм

  1. Создайте список последовательных целых чисел от 2 до n: (2, 3, 4,…, n).
  2. Первоначально, пусть я равен 2, наименьшее простое число.
  3. Перечислите кратные i, считая n с 2i с шагом i, и пометьте их как имеющие наименьший простой множитель как i (если он еще не отмечен). Также пометьте i как наименьший простой множитель i (i сам является простым числом).
  4. Найдите первое число больше, чем я в списке, который не отмечен. Если такого номера не было, остановитесь. В противном случае, позвольте мне теперь равняться этому новому числу (которое является следующим простым числом), и повторите с шага 3.

Ниже приведена реализация алгоритма, где less_prime [] сохраняет значение коэффициента наименьшего простого числа, соответствующего соответствующему индексу.

C / C ++

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

using namespace std;

  

void leastPrimeFactor(int n)

{

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

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

    vector<int> least_prime(n+1, 0);

  

    // Нам нужно вывести 1 для 1.

    least_prime[1] = 1;

  

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

    {

        // minimal_prime [i] == 0

        // означает, что я прост

        if (least_prime[i] == 0)

        {

            // отмечаем простое число

            // как свой собственный lpf

            least_prime[i] = i;

  

            // пометить его как делитель для всех его

            // умножается, если еще не отмечен

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

                if (least_prime[j] == 0)

                   least_prime[j] = i;

        }

    }

  

    // выводим множитель

    // чисел до n

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

        cout << "Least Prime factor of "

             << i << ": " << least_prime[i] << "\n";

}

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

int main()

{

    int n = 10;

    leastPrimeFactor(n);

    return 0;

}

Джава

// Java-программа для печати наименее простых факторов
// чисел меньше или равно
// n с использованием модифицированного сита эратосфена

  

import java.io.*;

import java.util.*;

  

class GFG

{

    public static void leastPrimeFactor(int n)

    {

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

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

        int[] least_prime = new int[n+1];

  

        // Нам нужно вывести 1 для 1.

        least_prime[1] = 1;

  

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

        {

            // minimal_prime [i] == 0

            // означает, что я прост

            if (least_prime[i] == 0)

            {

                // отмечаем простое число

                // как свой собственный lpf

                least_prime[i] = i;

  

                // пометить его как делитель для всех его

                // умножается, если еще не отмечен

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

                    if (least_prime[j] == 0)

                        least_prime[j] = i;

            }

        }

  

        // выводим множитель

        // чисел до n

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

            System.out.println("Least Prime factor of " +

                               + i + ": " + least_prime[i]);

    }

    public static void main (String[] args)

    {

        int n = 10;

        leastPrimeFactor(n);

    }

}

  
// Код предоставлен Mohit Gupta_OMG <(0_o)>

Python 3

# Программа Python 3 для печати
# наименьшие простые числа чисел
# меньше или равно n, используя
# модифицированное сито из эратосфена

  

def leastPrimeFactor(n) :

      

    # Создать вектор для хранения наименьшего числа простых чисел.

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

    least_prime = [0] * (n + 1)

  

    # Нам нужно напечатать 1 для 1.

    least_prime[1] = 1

  

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

          

        # priority_prime [i] == 0

        # означает, что я прост

        if (least_prime[i] == 0) :

              

            # маркировка простого числа

            # как свой собственный lpf

            least_prime[i] = i

  

            # пометить его как делитель для всех его

            # кратно, если еще не отмечено

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

                if (least_prime[j] == 0) :

                    least_prime[j] = i

          

          

    # выведите наименьший простой множитель

    количество номеров до n

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

        print("Least Prime factor of "

              ,i , ": " , least_prime[i] )

          

  
# Драйверная программа

  

n = 10

leastPrimeFactor(n)

  

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

C #

// C # программа для вывода наименьших простых множителей
// чисел меньше или равно
// n с использованием модифицированного сита эратосфена

using System;

  

class GFG

{

    public static void leastPrimeFactor(int n)

    {

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

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

        int []least_prime = new int[n+1];

  

        // Нам нужно вывести 1 для 1.

        least_prime[1] = 1;

  

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

        {

            // minimal_prime [i] == 0

            // означает, что я прост

            if (least_prime[i] == 0)

            {

                // отмечаем простое число

                // как свой собственный lpf

                least_prime[i] = i;

  

                // пометить его как делитель для всех его

                // умножается, если еще не отмечен

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

                    if (least_prime[j] == 0)

                        least_prime[j] = i;

            }

        }

  

        // выводим множитель

        // чисел до n

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

            Console.WriteLine("Least Prime factor of "

                               i + ": " + least_prime[i]);

    }

      

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

    public static void Main ()

    {

        int n = 10;

          

        // вызов функции

        leastPrimeFactor(n);

    }

}

  
// Этот код предоставлен Нитином Митталом

PHP

<?php
// PHP-программа для печати
// Наименьшие простые множители
// числа меньше или равны
// для использования модифицированного сита
// Эратосфена

  

function leastPrimeFactor($n)

{

    // Создать вектор для

    // сохранить наименьшее число простых чисел

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

    // как 0.

    $least_prime = array($n + 1);

      

    for ($i = 0; 

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

    $least_prime[$i] = 0;

      

    // Мы должны

    // выводим 1 для 1.

    $least_prime[1] = 1;

  

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

    {

        // minimal_prime [i] == 0

        // означает, что я прост

        if ($least_prime[$i] == 0)

        {

            // отмечаем простое число

            // номер как собственный lpf

            $least_prime[$i] = $i;

  

            // пометить его как делитель

            // для всех его кратных

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

            for ($j = 2 * $i;

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

                if ($least_prime[$j] == 0)

                $least_prime[$j] = $i;

        }

    }

  

    // выводим наименьшее простое число

    // коэффициент чисел

    // до п

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

        echo "Least Prime factor of " .

                            $i . ": "

               $least_prime[$i] . "\n";

}

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

$n = 10;

leastPrimeFactor($n);

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


Выход:

Least Prime factor of 1: 1
Least Prime factor of 2: 2
Least Prime factor of 3: 3
Least Prime factor of 4: 2
Least Prime factor of 5: 5
Least Prime factor of 6: 2
Least Prime factor of 7: 7
Least Prime factor of 8: 2
Least Prime factor of 9: 3
Least Prime factor of 10: 2

Сложность времени: O (nlog (n))
Вспомогательное пространство: O (n)

Ссылки:
1. http://espressocode.top/sieve-of-eratosthenes/
2. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
3. https://oeis.org/wiki/Least_prime_factor_of_n

Упражнение:
Можем ли мы расширить этот алгоритм или использовать less_prime [], чтобы найти все простые множители для чисел до n?

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

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

Наименьший простой множитель чисел до n

0.00 (0%) 0 votes