Магический массив A из N целых чисел с длиной K

Question

Учитывая массив A из N целых чисел , массив, называемый магическим, если все его элементы имеют ровно 3 делителя .Теперь вам нужно конвертировать данный массив в магический массив длиной K .Вы можете выполнять следующие операции в любом порядке времени.

1. Увеличить значение любого элемента массива на 1.

2. Уменьшить значение любого элемента массива на 1.

3. Удалить любой элемент массива.

Ограничения:

1 <= N <= 1000000
1 <= K <= N
1 <= A <= 1000000

Sample Input
5(size of the array) 3(K)
1 4 10 8 15

Output
4

Решение, которое я пробовал:

Итерировал каждый элемент массива, проверяя около квадрата простого числа и добавляя эту разницу к глобальной операции подсчета (переменная, используемая для подсчета требуемых операций).Этот порядок времени n ^ 2.

В поисках лучшего решения.

Answer 1

вы можете попробовать с помощью метода ниже, чтобы найти число с 3 делителями

void numbersWith3Divisors(int n) 
{ 
    boolean[] isPrime = new boolean[n+1]; 
    Arrays.fill(isPrime, true); 
    isPrime[0] = isPrime[1] = false; 

    for (int p=2; p*p<=n; p++) 
    { 
       if (isPrime[p] == true) 
        { 
            for (int i=p*2; i<=n; i += p) 
                isPrime[i] = false; 
        } 
    } 

    System.out.print("Numbers with 3 divisors :- "); 
    for (int i=0;  i*i <= n ; i++) 
        if (isPrime[i]) 
            System.out.print(i*i + " "); 
} 

то же самое вы можете применить для массива,

надеюсь, что это поможет

Answer 2

Создание массива с абсолютными значениями разностей с ближайшими простыми квадратами

Использование алгоритма QuickSelect для разделения K меньших различий (средняя сложность имеет тенденцию к O(N), а худшая квадратичнаявозможен случай)

Рассчитать их сумму