В среднем у числа в диапазоне 1..10^6 14 делителей, включая единицу (максимум - 240 делителей у 720720).
Предпосчитать все делители всех чисел диапазона можно очень быстро, даже на питоне.
Заводишь массив длины 10^6+1 и на запросах type 1/2 инкрементируешь/декрементируешь его ячейки, соответствующие делителям x (но только в том случае, если сам x прибывает/исчезает из коллекции, иначе не надо).
На запросах type 3 выясняешь, что в ячейке массива по индексу x.
А этот код оптимизировать не надо.