Количество наборов, возможных с использованием целых чисел из диапазона [2, N] с использованием заданных операций, которые находятся в отношении эквивалентности.

Учитывая целое число N , несколько раз выберите два различных целых числа из диапазона от 2 до N и, если их НОД больше 1, вставьте их в один и тот же набор, насколько это возможно. Множества, образованные в отношении эквивалентности. Следовательно, если целые числа a и b принадлежат одному и тому же множеству, а целые числа b и c принадлежат одному и тому же множеству, то говорят, что целые числа a и c также принадлежат к одной группе. Задача состоит в том, чтобы найти общее количество таких наборов, которые можно составить.

Примеры:

Input: N = 3 
Output: 2
Explanation: Sets formed are: {2}, {3}. They cannot be put in the same set because there GCD is 1.

Input: N = 9
Output : 3
Sets formed are : {2, 3, 4, 6, 8, 9}, {5}, {7}
As {2, 4, 6, 8} lies in same set and {3, 6, 9} also lies in same set. Hence, all these lie in one set together, because 6 is the common element in both the sets.

Подход: Идея решения задачи основана на следующем наблюдении, что все числа, меньшие или равные N/2 , принадлежат одному и тому же множеству, потому что, если в них умножить 2, они будут четными числами и имеют НОД больше 1 . с 2 . Таким образом, оставшиеся наборы образованы числами больше N/2 и являются простыми, потому что если они не простые, то существует число, меньшее или равное N/2, которое является делителем этого числа. Простые числа от 2 до N можно найти с помощью решета Эратосфена.

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

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