Vzaimno prostie chisla!!!

[wk-cof]

Kak naiti chislo vzaimno prostih chisel s H<10^12 i kolichestvo delitelei H???

[Lord Skill]

перебором

[wk-cof]

издеваешься??? 10^12 степень - перебором ты ее до старости вселенной делать будешь... Алгоритмы какие - нить кто - нить знает???

ну составь один раз таблицу простых чисел <10**12
а в дальнейшем на ее основе строй алгоритмы

[wk-cof]

Хм... Даже если на 1000 обычных чисел приходится 1 простое, то таблица будет содержать 10^12 / 1000 = 1000000000 миллион чисел. А алгоритма нахождения следующего простого числа еще никто не придумал. Есть решето Эратосфена и еще несколько методов, но все они основаны на последовательном исключении НЕ простых чисел.
А способ узнать число взаимнопростых я уже нашел - функция Эйлера.
С числом простых делителей сложнее...

[Ghost]

Для начала, хочешь - не хочешь, придется разложить число H на простые множители. После этого задача сводится к следующему: найти количество чисел меньших H, неделящихся ни на один из этих множителей. Решение этой задачи можно найти в книге "Ф.А.Новиков ДИСКРЕТНАЯ МАТЕМАТИКА ДЛЯ ПРОГРАММИСТОВ" (см. аттач).

Для нахождения простых делителей H<10**12 достаточно иметь таблицу всех простых <10**6 (Это существенно, т.к. время работы возрастает экспоненциально, если мне не изменяет память!)
Программка на питоне за полчаса выдала мне все простые числа до 1000000. Надо? (Программку, список простых чисел.)
Далее, перебирая все делители меньшие корня квадратного из H, находишь все его простые делители (предварительно проверив, а не является ли H само по себе простым).
А дальше уточняешь задание.

[Drakosha]

можеш уточнить насчет количетва делителей - что точно надо?

[Hex0gen]

wk-cof:
Найти число чисел, взаимно простых с N при небольшом числе N - это достаточно простая задача.
Есть, так называемая, Функция Эйлера. Функция Эйлера от числа N численно равна числу чисел меньших N и взаимно простых с N.

Если известно разложение числа N на простые множители, то Функция Эйлера вычисляется за полиномиальное время.

Итак, тебе нужно:
1. Найти разложение числа N на простые множители! Алгоритмов масса (ро-эвристика Полларда, квадратичное решето). Но, поскольку число N - мало (~10^12), то для простоты можно обойтись простым перебором (надо совершить всего ~10^6 делений).

2. Пусть N = (p1^e1)*(p2^e2)*...*(pk^ek), где p1, p2, ... , pk - простые числа.
Число чисел меньших N и взаимно простых с N равно:
F(N) = (p1^e1 - p1^(e1-1))*(p2^e2 - p2^(e2-1))*..*(pk^ek - pk^(ek-1))

Я тут маленькую программку написал, которая вычисляет Функцию Эйлера, если хочешь, коды кину.

Алгоритм вычисления Функции Эйлера прикладываю (:

[wk-cof]

to Hex0gen:
Спасибо, но я уже и сам это понял.

to moron:
А с простыми делителями - есть другой способ:Есть N<=10**12 сначала возьмем цифру 2. Если N на нее делится - делим его и проверяем снова, и так далее пока нацело оно на 2 делится уже не будет. берем следующую цифру, проверяем делимость. Смысл в том, что следующее число, на которое будет делиться N - простое. и так далее до N/2, или пока N не станет = 1. Махсимум(если число N - простое) нам прийдется сделат 10**6 - 1 операцию, а это для современной машины это не проблема.
Метод, показанный здесь имеет ту же основу, что и решето, но не требует создания огромного массива с простыми числами.