Я пытаюсь работать через Project Euler, и я нахожу барьер на проблеме 03. У меня есть алгоритм, который работает для меньших чисел, но проблема 3 использует очень и очень большое число.
Проблема 03: Основными факторами 13195 являются 5, 7, 13 и 29. Каков максимальный простой коэффициент числа 600851475143?
Вот мое решение в С#, и оно работает, я думаю, что около часа. Я не ищу ответа, потому что я действительно хочу решить это сам. В основном просто ищут помощь.
static void Main(string[] args) {
const long n = 600851475143;
//const long n = 13195;
long count, half, largestPrime = 0;
bool IsAPrime;
half = n / 2;
for (long i = half; i > 1 && largestPrime == 0; i--) {
if (n % i == 0) { // these are factors of n
count = 1;
IsAPrime = true;
while (++count < i && IsAPrime) {
if (i % count == 0) { // does a factor of n have a factor? (not prime)
IsAPrime = false;
}
}
if (IsAPrime) {
largestPrime = i;
}
}
}
Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
Console.ReadLine();
}
Для начала, вместо начала поиска в n/2, запустите его с квадратного корня из n. Вы получите половину факторов, а другая половина будет их дополнением.
например:
n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.
long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3;
while( n > 1)
{
if(n % factor == 0)
{
n/=factor;
}else
factor += 2; //skip even numbrs
}
print factor;
Это должно быть достаточно быстро... Обратите внимание, что нет необходимости проверять, просто ли...
Хотя вопрос задает самый большой простой коэффициент, это не обязательно означает, что вам нужно найти этот первый...
На самом деле, для этого случая вам не нужно проверять правильность, просто удалите факторы, которые вы найдете. Начните с n == 2 и сканируйте вверх. Когда evil-big-number% n == 0, разделите зло-большое число на n и продолжайте с числом меньшего зла. Остановитесь, когда n >= sqrt (big-evil-number).
Не требуется больше нескольких секунд на любой современной машине.
Вам нужно уменьшить количество проверок, которые вы делаете... подумайте о том, какие номера вам нужно проверить.
Для лучшего подхода прочитайте Сито Эратосфена... оно должно заставить вас указывать в правильном направлении.
Что касается причины принятого ответа на nicf:
Это нормально для проблемы в Euler, но не делает это эффективным решением в общем случае. Почему бы вам попробовать четные цифры для факторов?
Это приведет к следующему коду:
n = abs(number);
result = 1;
if (n mod 2 = 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i = 0) {
result = i;
while (n mod i = 0) n /= i;
}
}
return max(n,result)
Есть несколько modulo тестов, которые являются superflous, так как n никогда не может быть разделено на 6, если все факторы 2 и 3 были удалены. Вы могли бы разрешать простые числа для i.
В качестве примера рассмотрим результат для 21:
21 нет, поэтому мы переходим в цикл for с верхним пределом sqrt (21) (~ 4.6). Затем мы можем разделить 21 на 3, поэтому результат = 3 и n = 21/3 = 7. Теперь нам нужно проверить только до sqrt (7). который меньше 3, поэтому мы закончили цикл for. Мы возвращаем max n и результат, который равен n = 7.
То, как я это делал, это поиск простых чисел (p), начиная с 2, используя Сито Эратосфена. Этот алгоритм может найти все простые числа менее 10 миллионов в < 2s на прилично быстрой машине.
Для каждого найденного множителя тест делим его на число, которое вы тестируете, до тех пор, пока вы больше не сможете делать целочисленное деление. (т.е. проверьте n % p == 0 и если true, тогда разделите.)
Как только n = 1, все готово. Последнее значение n, которое успешно разделено, является вашим ответом. На боковой панели вы также нашли все основные факторы n на пути.
PS: Как отмечалось ранее, вам нужно искать простые числа между 2 <= n <= sqrt(p). Это делает сито Эратосфена очень быстрым и простым в использовании алгоритмом для наших целей.
Как только вы найдете ответ, введите в браузере следующее:)
http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)
Wofram Alpha - ваш друг
Использование рекурсивного алгоритма в Java выполняется менее секунды... подумайте о своем алгоритме, так как он включает в себя некоторые "грубые форсировки", которые можно устранить. Также посмотрите, как ваше пространство решения может быть уменьшено путем промежуточных вычислений.
Легкий peasy в С++:
#include <iostream>
using namespace std;
int main()
{
unsigned long long int largefactor = 600851475143;
for(int i = 2;;)
{
if (largefactor <= i)
break;
if (largefactor % i == 0)
{
largefactor = largefactor / i;
}
else
i++;
}
cout << largefactor << endl;
cin.get();
return 0;
}
Это решение на С++ заняло 3,7 мс на моем Intel Quad Core i5 iMac (3,1 ГГц)
#include <iostream>
#include <cmath>
#include <ctime>
using std::sqrt; using std::cin;
using std::cout; using std::endl;
long lpf(long n)
{
long start = (sqrt(n) + 2 % 2);
if(start % 2 == 0) start++;
for(long i = start; i != 2; i -= 2)
{
if(n % i == 0) //then i is a factor of n
{
long j = 2L;
do {
++j;
}
while(i % j != 0 && j <= i);
if(j == i) //then i is a prime number
return i;
}
}
}
int main()
{
long n, ans;
cout << "Please enter your number: ";
cin >> n; //600851475143L
time_t start, end;
time(&start);
int i;
for(i = 0; i != 3000; ++i)
ans = lpf(n);
time(&end);
cout << "The largest prime factor of your number is: " << ans << endl;
cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;
return 0;
}
Все проблемы проекта Эйлера должны занимать меньше минуты; даже неоптимизированная рекурсивная реализация в Python занимает менее секунды [0,09 сек. (cpu 4.3 ГГц)].
from math import sqrt
def largest_primefactor(number):
for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
q, r = divmod(number, divisor)
if r == 0:
#assert(isprime(divisor))
# recursion depth == number of prime factors,
# e.g. 4 has two prime factors: {2,2}
return largest_primefactor(q)
return number # number is a prime itself
вы можете увидеть это: Есть ли простой алгоритм, который может определить, является ли X простым, а не путать простого смертного программиста?
и мне нравится решение бурового раствора:
требуется "mathn.rb"
ставит 600851475143.prime_division.last.first
Я проверил его здесь
Возможно, это считается обманом, но одна возможность в haskell - написать (для записи я сам написал строки и не проверял потоки eulerproject);
import Data.Numbers.Primes
last (primeFactors 600851475143)
Попробуйте использовать Тест Primary Miller-Rabin, чтобы проверить, что число является простым. Это должно значительно ускорить процесс.
Другой подход состоит в том, чтобы сначала получить все простые числа до n/2, а затем проверить, равен ли модуль 0. Алгоритм, который я использую для получения всех простых чисел до n, можно найти здесь.