Project Euler - Problem 3

[mishadoff]

Project Euler - Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Permalink: http://projecteuler.net/problem=3

Знайти найбільший простий дільник числа 600851475143

Задачу можна робити в лоб. Для цього берем цикл від 1 і до нашого числа. Кожен індекс циклу перевіряємо:
просте, якщо ні ідем далі, якщо да, перевіряємо чи наше число ділиться націло, якщо ні йдемо далі, да - запамятовуємо його і йдемо далі (Перевірки можна переставити, так буде навіть оптимальніше). Проблема в тому, що складність такого алгоритму O(n) і перебирати 600 мільярдів буде дуже довго, не враховуючи навіть перевірки кожної ітерації. Набагато оптимальніше реалізувати цикл до корня з цього числа. Така оптимізація основана на тому факті, що якщо число a ділиться на b і дає якесь с, то воно очевидно ділиться і на с.
Числа b і a/b не можуть бути одночасно більшими за корінь а (тут вже матан) тому є сенс іти до корня. Це вже зменшує складність нашого алгоритму до O(sqrt(n)). Ще більший виграш у швидкості можна здобути, якщо в якості індексів ітерації брати вже готові прості числа.

Code:

1. (:use [clojure.contrib.lazy-seqs :only (primes)])
2. (:use [clojure.contrib.math :only (sqrt)])
3. (defn greatest-prime-of [number]
4.  (reduce max (filter #(zero? (mod number %))
5.   (take-while #(< % (sqrt number)) primes))))

* This source code was highlighted with Source Code Highlighter with my modifications.

Код вище використовує дві контрібовські ліби, а точніше лише дві функції з них (primes) і (sqrt).
1. (primes) - лінива послідовність простих чисел, з бібліотеки lazy-seqs на подобі послідовності фібоначчі, яку ми використовували в задачі 2.
2. (sqrt number) - корінь з числа.
3. (mod number1 number2) - знаходить остачу від ділення number1 на number2. Розумніша назва - сума по модулю.
4. Предикат zero? вертає true, якщо число дорівнює 0.

Links:
Prime numbers: http://en.wikipedia.org/wiki/Prime_number