Project Euler 214, как я могу сделать его более эффективным?

Question

Я становлюсь все более зависимым от проблем Project Euler. Однако с одной недели я застрял с # 214 .

Вот краткая версия проблемы: PHI () - это функция Эйлера, то есть для любого заданного целого числа n, PHI (n) = числа k <= n, для которых gcd (k, n) = 1. </p>

Мы можем использовать PHI () для создания цепочки. Например, начиная с 18:

PHI (18) = 6 => PHI (6) = 2 => PHI (2) = 1.

Итак, начиная с 18, мы получаем цепочку длиной 4 (18,6,2,1)

Задача состоит в том, чтобы вычислить сумму всех простых чисел, меньших 40e6, которые образуют цепочку длиной 25.

Я создал функцию, которая вычисляет длину цепочки любого числа, и протестировал ее для
небольших значений: она работает хорошо и быстро.
сумма всех простых чисел <= 20, порождающих цепочку длиной 4: 12 <br> сумма всех простых чисел <= 1000, порождающих цепочку длиной 10: 39383 <br>

К сожалению, мой алгоритм плохо масштабируется. Когда я применяю его к задаче, для его расчета требуется несколько часов ... поэтому я прекращаю его, потому что задачи Project Euler должны быть решены менее чем за одну минуту.

Я думал, что моя функция обнаружения простых чисел может быть медленной, поэтому я снабдил программу списком простых чисел <40e6, чтобы избежать проверки на простоту ... Теперь код работает немного быстрее, но до сих пор нет способа его получить. решение менее чем за несколько часов (и я не хочу этого). </p>

Так есть ли какой-нибудь "магический трюк", который мне здесь не хватает? Я действительно не понимаю, как быть более эффективным в этом ...

Я не спрашиваю о решении, потому что борьба с оптимизацией - это все удовольствие от Project Euler. Тем не менее, любой небольшой намек, который может поставить меня на правильный путь, будет приветствоваться.

Спасибо!

---

Извините, неправильное форматирование комментария, и я не могу его удалить. И вот снова:

Для вычисления функции totoent я использую следующее: Для данного n, давайте назовем p списком его факторов.
фи (n) = n * прод ((p-1) / p)

например: 2,3 - это коэффициенты 18 => фи (18) = 18 * 1/2 * 2/3 = 6

Таким образом, я не вычисляю gcd. Функция, которая дает мне факторы, встроена в MATLAB (да, я забыл упомянуть, что я кодирую в Matlab). Может быть, мне следует переписать функцию факторизации ...

Answer 1

Подсказки :

1. Используйте памятку и не рассчитывайте phi(n) более одного раза.

2. Попробуйте использовать значения phi(), которые вы уже рассчитали для меньшего n, при расчете фи (N). Что-то вроде phi(m*n) = phi(m) * phi(n) [Какое свойство должны иметь m и n для этого?]

3. Вы знаете, что такое phi(p), когда p простое число ?

Answer 2

Попробуйте вернуться назад ... (начните с 1, 2 и т. Д. И двигайтесь вверх, а не пытаться вернуться назад и связать в цепочки)

edit: также обратите внимание, что totient (x) имеет особую структуру , а именно totient (x) = x * произведение (1- (1 / p)), где p - различные простые факторы что делят х.

Answer 3

Я сделаю дикое предположение, что отнимающая много времени часть вычисляет числа чисел.

Одной мыслью может быть попытка сгенерировать их каким-нибудь умным способом. Подумайте, можно ли рассчитать их все сразу, вместо того, чтобы вычислять одно число за раз ...

Кроме того, как вы рассчитываете функцию totient? Определение (число целых чисел k, где gcd (n, k) == 1) не является полезным способом работы с ним. Найдите его и посмотрите, сможете ли вы найти для него более подходящую формулу.

Edit: Да, это выражение, которое я был после. Но прохождение каждого целого числа, его разложение и вычисление значения слишком медленное. Ищите способ вычислить табличные элементы без какого-либо факторинга ...

Answer 4

Ну, я не знаком с этим, и вы не показываете, что делаете ... но некоторые мысли:

• упростить gcd; вам не нужно знать ответ - просто существует ли какой-либо общий фактор - поэтому разложите на множители меньшее число (из списка простых чисел) и сравните каждый член с большим числом

Answer 5

Я не решил это, но я думаю, что вы могли бы быть на правильном пути с вашей схемой кэширования, вы просто не могли бы кэшировать правильные вещи. Надеюсь, это не слишком много или слишком неясный «намек» для вас.

Answer 6

Одна вещь, которую нужно понять, это то, что когда вы достигнете 6, например, остальная часть цепочки всегда будет 2,1.