Вам надо найти количество пар или сами пары?

Если найти количество таких пар, то решение простое.

Сначала перебираем первое число пары — A = 1 .. sqrt(N)

Потом мы можем узнать диапазон, в который может входить второе число пары — B = A .. R, где R = N / A. (Будем считать что A < B)

Теперь мы должны уметь решать такую подзадачу:

Подсчет всех взаимно простых с числом A на промежутке A .. R

Это решается так(с помощью принципа включения-исключения):

Мы должны узнать все простые делители числа A, их не больше, чем log(A).

Теперь мы должны сформировать все возможные произведения из этих простых чисел.

Пусть этих простых чисел M.

Тогда мы должны перебрать все маски mask = 0 .. 2^(M) — 1 где i-ый бит маски будет означать, что мы включили i-ое простое число в произведение.

Теперь нам для каждого произведения надо посчитать кол-во чисел которое делится на него, на отрезке A .. R. (это делается простыми делениями, то есть R/prod — (A-1)/prod, где prod — наше произведение).

Теперь, получив кол-во чисел которые делятся на prod, мы должны прибавить или отнять от кол-ва взаимно простых(оно у нас вначале равно длине промежутка, на котором ищем кол-во взаимно простых), в зависимости от кол-ва единичных бит в маске, которую перебираем. Если число единичных бит в маске нечетное, то отнимаем кол-во чисел которые делятся на prod, иначе прибавляем(это и есть то место, где применяем принцип включений-исключений).

Всё мы решили задачу о нахождении взаимно простых на отрезке.

Следовательно мы решили всю задачу.

асимптотика: N^(1/2+1/3), но на самом деле это завышенная асимптотика :)

Для того, чтобы более понять, что я тут написал, советую почитать эту статью

Все пары вы врядли найдете. Их уж никак не меньше, чем N