Помощь по проекту Эйлера, вопрос 3
https://stackoverflow.com/questions/201374
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь работать над проектом Эйлера и натыкаюсь на барьер в задаче 03.У меня есть алгоритм, который работает для меньших чисел, но в задаче 3 используются очень и очень большие числа.
Проблема 03:Простые делители числа 13195 — 5, 7, 13 и 29.Каков наибольший простой делитель числа 600851475143?
Вот мое решение на C#, и оно работает, кажется, около часа.Я не ищу ответа, потому что на самом деле хочу решить эту проблему сам.В основном просто ищу помощи.
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 и просматривайте вверх.Когда большое-злое число % n == 0, разделите большое-злое-число на n и продолжите с меньшим-злым-числом.Остановитесь, когда n >= sqrt(big-evil-number).
На любой современной машине это не должно занимать более нескольких секунд.
Хотя вопрос требует крупнейший главный фактор, это не обязательно означает, что вам нужно сначала найти его...
Вам нужно уменьшить количество проверок, которые вы делаете...подумайте, какие цифры вам нужно проверить.
Для лучшего подхода прочитайте Решето Эратосфена ...это должно направить вас в правильном направлении.
Что касается причины принятого ответа nicf:
Это нормально для задачи Эйлера, но не делает это эффективным решением в общем случае.Зачем вам пытаться использовать четные числа в качестве факторов?
- Если n ровно, переключите влево (разделите на 2), пока это больше не станет.Если это одно, то 2 является самым большим основным фактором.
- Если n нет, вам не нужно тестировать четные числа.
- Это правда, что вы можете остановиться в SQRT (n).
- Вам нужно только проверить простые числа на факторы.Может быть быстрее проверить, делит ли K, а затем проверить его на первичность.
- Вы можете оптимизировать верхний предел на лету, когда найдете фактор.
Это приведет к такому коду:
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)
Есть некоторые проверки по модулю, которые являются излишними, поскольку n никогда не может быть разделено на 6, если удалены все множители 2 и 3.Вы можете разрешить только простые числа для i.
В качестве примера давайте посмотрим на результат для 21:
21 не четное, поэтому мы переходим в цикл for с верхним пределом sqrt(21) (~4,6).Затем мы можем разделить 21 на 3, поэтому результат = 3 и n = 21/3 = 7.Теперь нам осталось протестировать только sqrt(7).которое меньше 3, поэтому мы закончили с циклом for.Мы возвращаем максимальное значение n и результат: n = 7.
Я это сделал для поиска простых чисел (p), начиная с 2, используя Решето Эратосфена.Этот алгоритм может найти все простые числа до 10 миллионов менее чем за 2 секунды на достаточно быстрой машине.
Для каждого найденного простого числа тестируйте деление его на число, которое вы проверяете, до тех пор, пока вы больше не сможете выполнять целочисленное деление.(т.е.проверять n % p == 0 и если верно, то разделите.)
Один раз n = 1, все готово.Последнее значение n что успешно разделено – вот ваш ответ.Кстати, вы также нашли все основные факторы n в пути.
ПС:Как было отмечено ранее, вам нужно искать только простые числа между 2 <= n <= sqrt(p).Это делает решето Эратосфена очень быстрым и простым в реализации алгоритмом для наших целей.
Как только вы найдете ответ, введите следующее в своем браузере ;)
http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)
Вофрам Альфа — твой друг
Использование рекурсивного алгоритма в Java выполняется менее секунды...Немного продумайте свой алгоритм, поскольку он включает в себя некоторый «грубый принудительный подход», который можно устранить.Также посмотрите, как можно уменьшить пространство вашего решения с помощью промежуточных вычислений.
Легко на C++:
#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;
}
Это решение на C++ заняло 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 секунды (процессор 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 простым, и не запутать простого смертного программиста?
и мне нравится решение Lill Mud:
требуется "mathn.rb"
ставит 600851475143.prime_division.last.first
я проверил это здесь
Возможно, это считается мошенничеством, но одна из возможностей в Haskell — написать (к сведению, я сам написал строки и не проверял потоки eulerproject);
import Data.Numbers.Primes
last (primeFactors 600851475143)
Попробуйте использовать Тест на простоту Миллера-Рабина проверить, является ли число простым.Это должно значительно ускорить процесс.
Другой подход — сначала получить все простые числа до n/2, а затем проверить, равен ли модуль 0.Алгоритм, который я использую, чтобы получить все простые числа до н может быть найден здесь.
