Рубрики

Найдите простое число K в массиве так, чтобы (A [i]% K) было максимально

Дан массив arr [] из n целых чисел. Задача состоит в том, чтобы найти элемент из массива K такой, что

  1. К простое число .
  2. И, arr [i]% K является максимальным для всех действительных i среди всех возможных значений K

если в массиве нет простого числа, выведите -1 .

Примеры:

Input: arr[] = {2, 10, 15, 7, 6, 8, 13}
Output: 13
2, 7 and 13 are the only prime numbers in the array.
The maximum possible value of arr[i] % 2 is 1 i.e. 15 % 2 = 1.
For 7, it is 6 % 7 = 6
For 13, 10 % 13 = 10 (Maximum possible)

Input: arr[] = {23, 13, 6, 2, 15, 18, 8}
Output: 23

Подход: чтобы максимизировать значение arr [i]% K , K должно быть максимальным простым числом из массива, а arr [i] должно быть наибольшим элементом из массива, который меньше K. Итак, теперь проблема сводится к поиску максимального простого числа из массива. Чтобы сделать это,

  1. Сначала найдите все простые числа, меньшие или равные максимальному элементу из массива, используя Sieve .
  2. Затем найдите максимальное простое число из массива и распечатайте его. Если в массиве нет простого числа, выведите -1.

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата требуемого
// простое число из массива

int getPrime(int arr[], int n)

{

    // Находим максимальное значение в массиве

    int max_val = *max_element(arr, arr + n);

  

    // ИСПОЛЬЗУЕМ СИТУ, ЧТОБЫ НАЙТИ ВСЕ ПЕРВЫЕ НОМЕРА

    // ЧЕМ ИЛИ РАВНЫМ К max_val

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

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

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

    vector<bool> prime(max_val + 1, true);

  

    // Оставшаяся часть СИТА

    prime[0] = false;

    prime[1] = false;

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

  

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

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

        if (prime[p] == true) {

  

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

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

                prime[i] = false;

        }

    }

  

    // Для сохранения максимального простого числа

    int maximum = -1;

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

  

        // Если текущий элемент прост

        // затем обновляем максимальное простое число

        if (prime[arr[i]])

            maximum = max(maximum, arr[i]);

    }

  

    // Возвращаем максимальное простое число

    // номер из массива

    return maximum;

}

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

int main()

{

    int arr[] = { 2, 10, 15, 7, 6, 8, 13 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    cout << getPrime(arr, n);

  

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

  
// Функция для возврата требуемого
// простое число из массива

static int getPrime(int arr[], int n)

{

    // Находим максимальное значение в массиве

    int max_val = Arrays.stream(arr).max().getAsInt();

  

    // ИСПОЛЬЗУЕМ СИТУ, ЧТОБЫ НАЙТИ ВСЕ ПЕРВЫЕ НОМЕРА

    // ЧЕМ ИЛИ РАВНЫМ К max_val

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

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

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

    Vector<Boolean> prime = new Vector<>(max_val + 1);

    for(int i = 0; i < max_val + 1; i++)

        prime.add(i,Boolean.TRUE);

  

    // Оставшаяся часть СИТА

    prime.add(1,Boolean.FALSE);

    prime.add(2,Boolean.FALSE);

    for (int p = 2; p * p <= max_val; p++) 

    {

  

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

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

        if (prime.get(p) == true

        {

  

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

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

                prime.add(i,Boolean.FALSE);

        }

    }

  

    // Для сохранения максимального простого числа

    int maximum = -1;

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

    {

  

        // Если текущий элемент прост

        // затем обновляем максимальное простое число

        if (prime.get(arr[i]))

        {

            maximum = Math.max(maximum, arr[i]);

        }

              

    }

  

    // Возвращаем максимальное простое число

    // номер из массива

    return maximum;

}

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

public static void main(String[] args) 

{

    int arr[] = { 2, 10, 15, 7, 6, 8, 13 };

    int n = arr.length;

  

    System.out.println(getPrime(arr, n));

}
}

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

python3

# Python 3 реализация подхода

from math import sqrt

  
# Функция для возврата необходимого
# простое число из массива

def getPrime(arr, n):

      

    # Найти максимальное значение в массиве

    max_val = arr[0]

    for i in range(len(arr)):

          

        # ИСПОЛЬЗУЙТЕ СИТА, ЧТОБЫ НАЙТИ ВСЕ ПЕРВЫЕ НОМЕРА

        # ЧЕМ ИЛИ РАВНЫМ max_val

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

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

        # если я не простое число, иначе верно.

        if(arr[i] > max_val):

            max_val = arr[i]

  

    prime = [True for i in range(max_val + 1)]

   

    # Оставшаяся часть СИТА

    prime[0] = False

    prime[1] = False

    for p in range(2, int(sqrt(max_val)) + 1, 1):

          

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

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

        if (prime[p] == True):

              

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

            for i in range(p * 2, max_val + 1, p):

                prime[i] = False

  

    # Хранить максимальное простое число

    maximum = -1

    for i in range(n):

          

        # Если текущий элемент является простым

        # затем обновите максимальное простое число

        if (prime[arr[i]]):

            maximum = max(maximum, arr[i])

  

    # Вернуть максимальное простое число

    # номер из массива

    return maximum

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

if __name__ == '__main__':

    arr = [2, 10, 15, 7, 6, 8, 13]

    n = len(arr)

  

    print(getPrime(arr, n))

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

C #

// C # реализация подхода

using System; 

using System.Linq;

using System.Collections.Generic; 

      

class GFG

{

  
// Функция для возврата требуемого
// простое число из массива

static int getPrime(int []arr, int n)

{

    // Находим максимальное значение в массиве

    int max_val = arr.Max();

  

    // ИСПОЛЬЗУЕМ СИТУ, ЧТОБЫ НАЙТИ ВСЕ ПЕРВЫЕ НОМЕРА

    // ЧЕМ ИЛИ РАВНЫМ К max_val

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

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

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

    List<Boolean> prime = new List<Boolean>(max_val + 1);

    for(int i = 0; i < max_val + 1; i++)

        prime.Insert(i, true);

  

    // Оставшаяся часть СИТА

    prime.Insert(1, false);

    prime.Insert(2, false);

    for (int p = 2; p * p <= max_val; p++) 

    {

  

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

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

        if (prime[p] == true

        {

  

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

            for (int i = p * 2; 

                     i <= max_val; i += p)

                prime.Insert(i, false);

        }

    }

  

    // Для сохранения максимального простого числа

    int maximum = -1;

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

    {

  

        // Если текущий элемент прост

        // затем обновляем максимальное простое число

        if (prime[arr[i]])

        {

            maximum = Math.Max(maximum, arr[i]);

        }

              

    }

  

    // Возвращаем максимальное простое число

    // номер из массива

    return maximum;

}

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

public static void Main(String[] args) 

{

    int []arr = { 2, 10, 15, 7, 6, 8, 13 };

    int n = arr.Length;

  

    Console.WriteLine(getPrime(arr, n));

}
}

  
// Этот код предоставлен Rajput-Ji

PHP

<?php
// PHP реализация подхода

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

function getPrime($arr, $n

    // Находим максимальное значение в массиве

    $max_val = max($arr); 

  

    // ИСПОЛЬЗУЕМ СИТУ, ЧТОБЫ НАЙТИ ВСЕ ПЕРВЫЕ НОМЕРА

    // ЧЕМ ИЛИ РАВНЫМ К max_val

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

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

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

    $prime = array_fill(0, $max_val + 1, true); 

  

    // Оставшаяся часть СИТА

    $prime[0] = false; 

    $prime[1] = false; 

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

    

  

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

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

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

        

  

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

            for ($i = $p * 2; $i <= $max_val; $i += $p

                $prime[$i] = false; 

        

    

  

    // Для сохранения максимального простого числа

    $maximum = -1; 

      

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

    

  

        // Если текущий элемент прост

        // затем обновляем максимальное простое число

        if ($prime[$arr[$i]]) 

            $maximum = max($maximum, $arr[$i]); 

    

  

    // Возвращаем максимальное простое число

    // номер из массива

    return $maximum

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

$arr = array( 2, 10, 15, 7, 6, 8, 13 ); 

$n = count($arr) ; 

  

echo getPrime($arr, $n); 

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

Выход:

13

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

Найдите простое число K в массиве так, чтобы (A [i]% K) было максимально

0.00 (0%) 0 votes