Найдите простые множители Z такие, что Z является произведением всех четных чисел до N, которые являются произведением двух различных простых чисел.

Для заданного числа N (N > 6) задача состоит в том, чтобы напечатать простую факторизацию числа Z , где Z — произведение всех чисел ≤ N , которые четны и можно представить как произведение двух различных простых чисел.

Пример:

Input: N = 6
Output: 2→1
               3→1
Explanation: 6 is the only number ≤ N, which is even and a product of two distinct prime numbers (2 and 3). Therefore, Z=6. 
Now, prime factorization of Z=2×3

Input: N = 5
Output: 2→2
               3→1
               5→1
Explanation: The only even numbers ≤N, which can be expressed as the product of two distinct prime numbers, are 6 (2×3) and 10 (2×5). Therefore, Z = 6*10=60 = 2x2x3x5

Наблюдение: Следующее наблюдение помогает решить проблему:

1. Поскольку требуемые числа должны быть четными и быть произведением двух различных простых чисел, они будут иметь вид 2×P , где P — простое число ≤ N/2.
2. Таким образом, простая факторизация Z будет иметь вид 2 ^x .3 ¹ .5 ¹ … P ¹ , где P — последнее простое число ≤ N/2 , а X — количество простых чисел в интервале [3, N / 2].

Подход: выполните шаги, чтобы решить проблему:

1. Сохраните все простые числа ≤ N/2 , используя решето Эратосфена, в векторе, скажем, простом .
2. Сохраните количество простых чисел в диапазоне [3, N/2] в переменной, скажем, x .
3. Выведите разложение простых чисел, где коэффициент 2 равен x , а коэффициенты всех остальных простых чисел в диапазоне [3, N/2] равны 1.

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

Временная сложность: O(N * log(log(N)))
Вспомогательное пространство: O(N)