Количество способов выбрать простое или не простое число на основе индекса массива

Опубликовано: 19 Сентября, 2022

Дан массив A[] размера N . Массив должен быть создан с использованием данного массива с учетом следующих условий.

  • Если индекс простой, вы должны выбрать не простое число меньше или равно A[i] .
  • Если индекс не является простым, вы должны выбрать простое число, которое меньше или равно A[i] .

Задача состоит в том, чтобы подсчитать общее количество способов, которыми можно выбрать такие числа.

Примечание . Индексацию данного массива следует рассматривать как индексацию на основе 1.

Примеры:

Input: N = 5  A = {2, 3, 4, 8, 5}
Output:  16
Explanation:  You can choose 1 number for index 1 i.e., 2 
(As index 1 is not prime and prime number count less than 
or equal to 2 is one i.e. 2), 1 number for index 2,  
2 numbers for index 3, 4 numbers for index 4 
and 2 numbers for index 5. 
Hence total number of ways = 1x1x2x4x2 = 16.

Input: N = 2  A = {5, 6}
Output:  9
Explanation:  You can choose 3 number for index 1,  
3 numbers for index 2. Hence total number of ways = 3×3 = 9 .

Подход: Идея решения проблемы заключается в следующем:

  • Counting and store the value of all non-prime and prime in an array till the maximum element of the array. 
  • Then iterate the given array and then if index i is non-prime we multiply the prime count till A[i] and perform the similar operation for prime index.

Следуйте приведенной ниже иллюстрации для лучшего понимания

Иллюстрация:

Consider an example N = 5 and A[] = {2, 3, 4, 8, 5}

As index 1 is Non Prime So Prime number count less than or equal to 2 is 1 (i.e 2) 
As index 2 is Prime So Non Prime number count less than or equal to 3 is 1 (i.e 1)
As index 3 is Prime So Non Prime number count less than or equal to 4 is 2 (i.e 1, 4)
As index 4 is Non Prime So Prime number count less than or equal to 8 is 4 (i.e 2, 3, 5, 7)
As index 5 is Prime So Non Prime number count less than or equal to 5 is 2 (i.e 1, 4)

Total Number of ways = 1 x 1 x 2 x 4 x 2 = 16 

Hence Total number of ways to select number from array is 16.      

Следуйте шагам, указанным ниже, чтобы реализовать идею

  • Найдите максимальное число из заданного массива.
  • Итерируйте от 1 до максимального значения и найдите количество простых и не простых чисел до каждого значения и сохраните их в векторе пар.
  • Перебрать массив:
    • Проверьте, является ли текущий индекс простым или непростым. если текущий индекс является простым, выберите счетчик непростых значений из вектора пары.
    • Умножьте ответ на число, не являющееся простым, и снова сохраните эти значения в ответе.
    • Если текущий индекс не является простым, выберите количество простых значений из вектора пары, умножьте на ответ и снова сохраните эти значения в ответе.
  • Вернуть ответ.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * sqrt (M)), где M — самый большой элемент массива.
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ