Рубрики

N-й умный номер

По заданному номеру n найдите умное число n (1 <= n <= 1000). Умный номер — это число, в котором есть как минимум три различных простых фактора. Нам дан верхний предел значения результата как MAX

Например, 30 — это 1-е умное число, потому что оно имеет 2, 3, 5, так как это различные простые факторы. 42 — это 2-е умное число, потому что оно имеет 2, 3, 7, так как это различные простые факторы.
Примеры:

Input : n = 1
Output: 30
// three distinct prime factors 2, 3, 5

Input : n = 50
Output: 273
// three distinct prime factors 3, 7, 13

Input : n = 1000
Output: 2664
// three distinct prime factors 2, 3, 37

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

  • Возьмите массив простых чисел [] и инициализируйте его 0.
  • Теперь мы знаем, что первое простое число равно i = 2, поэтому отметим простые числа [2] = 1 т.е. primes [i] = 1 указывает, что 'i' является простым числом.
  • Теперь пройдитесь по массиву простых чисел [] и пометьте все кратные 'i' условными простыми числами [j] — = 1, где 'j' кратно 'i', и проверьте простые условия [j] +3 = 0, потому что всякий раз, когда простые числа [j] становится -3, это означает, что ранее он был кратен трем различным основным факторам. Если простые условия [j] + 3 = 0 становятся истинными, это означает, что «j» является умным числом, поэтому сохраните его в массиве result [].
  • Теперь сортируйте массив result [] и возвращайте результат [n-1].

Ниже приведена реализация вышеуказанной идеи.

C ++

// реализация C ++ для поиска умного числа
#include<bits/stdc++.h>

using namespace std;

  
// Ограничение на результат

const int MAX = 3000;

  
// Функция для вычисления умного числа

int smartNumber(int n)

{

    // Инициализируем все числа как не простые

    int primes[MAX] = {0};

  

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

    vector<int> result;

  

    // Обходим все числа до максимального предела

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

    {

        // 'i' обозначается как простое число, потому что

        // оно не кратно любому другому простому числу

        if (primes[i] == 0)

        {

            primes[i] = 1;

  

            // помечаем все кратные 'i' как не простые

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

            {

                primes[j] -= 1;

  

                // Если я - третий простой множитель j

                // затем добавляем его в результат, как в

                // минимум три основных фактора.

                if ( (primes[j] + 3) == 0)

                    result.push_back(j);

            }

        }

    }

  

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

    sort(result.begin(), result.end());

  

    // возвращаем умный номер

    return result[n-1];

}

  
// Драйвер программы для запуска дела

int main()

{

    int n = 50;

    cout << smartNumber(n);

    return 0;

}

Джава

// Реализация Java для поиска умного номера

import java.util.*;

import java.lang.*;

  

class GFG {

  

    // Ограничение на результат

    static int MAX = 3000;

  

    // Функция для вычисления умного числа

    public static int smartNumber(int n)

    {

          

        // Инициализируем все числа как не простые

        Integer[] primes = new Integer[MAX];

        Arrays.fill(primes, new Integer(0));

  

        // итерация, чтобы отметить все простые и умные

        // число

        Vector<Integer> result = new Vector<>();

  

        // Обходим все числа до максимума

        // предел

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

        {

              

            // 'i' обозначается как простое число

            // потому что это не кратно

            // любое другое простое число

            if (primes[i] == 0)

            {

                primes[i] = 1;

  

                // помечаем все кратные 'i'

                // как не простое

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

                {

                    primes[j] -= 1;

      

                    // Если я - третье простое число

                    // фактор j затем добавить его

                    // чтобы получить результат как у

                    // минимум три основных фактора.

                    if ( (primes[j] + 3) == 0)

                        result.add(j);

                }

            }

        }

  

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

        Collections.sort(result);

  

        // возвращаем умный номер

        return result.get(n-1);

  

    }

  

    // Драйвер программы для запуска дела

    public static void main(String[] args)

    {

        int n = 50;

        System.out.println(smartNumber(n));

  

    }

}

  
// Этот код предоставлен Prasad Kshirsagar

python3

# Реализация Python3 для поиска
# умный номер

  
# Ограничение на результат

MAX = 3000

  
# Функция для вычисления n
# умный номер

def smartNumber(n): 

  

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

    primes = [0] * MAX

  

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

    # и умный номер

    result = []; 

  

    # Пройдите все числа до максимального предела

    for i in range(2, MAX): 

          

        # 'i' обозначается как простое число, потому что

        # это не кратно любому другому простому числу

        if (primes[i] == 0): 

            primes[i] = 1

  

            # пометить все кратные 'i' как не простые

            j = i * 2;

            while (j < MAX): 

                primes[j] -= 1

  

                # Если я - третий главный фактор j

                # затем добавьте его в результат, как в

                # как минимум три основных фактора.

                if ( (primes[j] + 3) == 0): 

                    result.append(j);

                j = j + i;

  

    # Сортировать все умные номера

    result.sort(); 

  

    # вернуть умный номер

    return result[n - 1]; 

  
Код водителя

n = 50

print(smartNumber(n)); 

  
# Этот код предоставлен mits

C #

// реализация C # для поиска n-го умного номера

using System.Collections.Generic;

  

class GFG {

  

    // Ограничение на результат

    static int MAX = 3000;

  

    // Функция для вычисления умного числа

    public static int smartNumber(int n)

    {

          

        // Инициализируем все числа как не простые

        int[] primes = new int[MAX];

  

        // итерация, чтобы отметить все простые и умные

        // число

        List<int> result = new List<int>();

  

        // Обходим все числа до максимума

        // предел

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

        {

              

            // 'i' обозначается как простое число

            // потому что это не кратно

            // любое другое простое число

            if (primes[i] == 0)

            {

                primes[i] = 1;

  

                // помечаем все кратные 'i'

                // как не простое

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

                {

                    primes[j] -= 1;

      

                    // Если я - третье простое число

                    // фактор j затем добавить его

                    // чтобы получить результат как у

                    // минимум три основных фактора.

                    if ( (primes[j] + 3) == 0)

                        result.Add(j);

                }

            }

        }

  

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

        result.Sort();

  

        // возвращаем умный номер

        return result[n-1];

  

    }

  

    // Драйвер программы для запуска дела

    public static void Main()

    {

        int n = 50;

        System.Console.WriteLine(smartNumber(n));

  

    }

}

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

PHP

<?php
// Реализация PHP для поиска умного номера

  
// Ограничение на результат

$MAX = 3000; 

  
// Функция для вычисления умного числа

function smartNumber($n

{

    global $MAX;

    // Инициализируем все числа как не простые

    $primes=array_fill(0,$MAX,0); 

  

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

    $result=array(); 

  

    // Обходим все числа до максимального предела

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

    

        // 'i' обозначается как простое число, потому что

        // оно не кратно любому другому простому числу

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

        

            $primes[$i] = 1; 

  

            // помечаем все кратные 'i' как не простые

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

            

                $primes[$j] -= 1; 

  

                // Если я - третий простой множитель j

                // затем добавляем его в результат, как в

                // минимум три основных фактора.

                if ( ($primes[$j] + 3) == 0) 

                    array_push($result,$j); 

            

        

    

  

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

    sort($result); 

  

    // возвращаем умный номер

    return $result[$n-1]; 

  
// Драйвер программы для запуска дела

  

    $n = 50; 

    echo smartNumber($n); 

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

Выход:

273

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

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

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

N-й умный номер

0.00 (0%) 0 votes