Задача Эйлера № 4

Question

Используя Python, я пытаюсь решить проблему # 4 проблемы Project Euler . Может кто-нибудь сказать, пожалуйста, что я делаю неправильно? Проблема состоит в том, чтобы найти самый большой палиндром из двух трехзначных чисел . Вот что я имею до сих пор.

import math

def main(): 
    for z in range(100, 1000):
        for y in range(100, 1000):
            for x in range(1, 1000000):
                x = str(x)
                if x == x[::-1] and x == z*y:
                    print x 

if __name__ == '__main__':
    main()

Answer 1

Другой совет здесь великолепен. Этот код также работает. Я начинаю с 999, потому что мы знаем, что самая большая возможная комбинация - 999 * 999. Не Python, но некоторые быстро сделали псевдокод.

public static int problem4()
    {       
    int biggestSoFar=0;
        for(int i = 999; i>99;i--){
            for(int j=999; j>99;j--){
                if(isPaladrome(i*j))
                   if(i*j>biggestSoFar)
                        biggestSoFar=i*j;
            }
        }
        return biggestSoFar;    
    }

Answer 2

Вот что я сделал в Java:

public class Euler0004
{
    //assumes positive int
    static boolean palindrome(int p)
    {
        //if there's only one char, then it's
        //  automagically a palindrome
        if(p < 10)
            return true;

        char[] c = String.valueOf(p).toCharArray();

        //loop over the char array to check that
        //  the chars are an in a palindromic manner
        for(int i = 0; i < c.length / 2; i++)
            if(c[i] != c[c.length-1 - i])
                return false;

        return true;
    }


    public static void main(String args[]) throws Exception
    {
        int num;
        int max = 0;

        //testing all multiples of two 3 digit numbers.
        // we want the biggest palindrome, so we
        // iterate backwards
        for(int i = 999; i > 99; i--)
        {
            // start at j == i, so that we
            //  don't calc 999 * 998 as well as
            //  998 * 999...
            for(int j = i; j > 99; j--)
            {
                num = i*j;

                //if the number we calculate is smaller
                //  than the current max, then it can't
                //  be a solution, so we start again
                if(num < max)
                    break;

                //if the number is a palindrome, and it's
                //  bigger than our previous max, it
                //  could be the answer
                if(palindrome(num) && num > max)
                    max = num;
            }
        }

        //once we've gone over all of the numbers
        //  the number remaining is our answer
        System.out.println(max);

    }
}

Answer 3

Если ваша программа работает медленно, и у вас есть такие циклы:

for z in range(100, 1000):
    for y in range(100, 1000):
        for x in range(1, 1000000):

Тогда вопрос, который вы должны задать себе: «Сколько раз будет выполняться тело самого внутреннего цикла?» (тело вашего внутреннего цикла - это код, начинающийся с: x = str(x))

В этом случае это легко понять. Внешний цикл будет выполнен 900 раз. Для каждой итерации средний цикл также будет выполняться 900 раз, что составляет 900 × 900 или 810 000 раз. Затем для каждой из этих 810 000 итераций внутренний цикл будет выполнен 999 999 раз. Я думаю, мне нужно долго, чтобы рассчитать, что:

>>> 900*900*999999
809999190000L

Другими словами, вы проводите проверку палиндрома почти 810 миллиардов раз. Если вы хотите включить рекомендуемый лимит Project Euler в 1 минуту для каждой проблемы, вы можете немного оптимизировать :-) (см. Комментарий Дэвида)

Answer 4

Вопрос гласит:

What is the largest prime factor of the number 600851475143?

Я решил это с помощью C #, но сам алгоритм не зависит от языка.

1. Создать метод определения, является ли число простым или нет. Это может быть перебор (а не использование гораздо более эффективного алгоритма просеивания), и он выглядит следующим образом:

---

private static long IsPrime(long input)
        {
            if ((input % 2) == 0)
            {
                return 2;
            }
            else if ((input == 1))
            {
                return 1;
            }
            else
            {
                long threshold = (Convert.ToInt64(Math.Sqrt(input)));
                long tryDivide = 3;
                while (tryDivide < threshold)
                {
                    if ((input % tryDivide) == 0)
                    {
                        Console.WriteLine("Found a factor: " + tryDivide);
                        return tryDivide;
                    }
                    tryDivide += 2;
                }
                Console.WriteLine("Found a factor: " + input);
                return -1;
            }
        }

2. Если у меня есть функция для определения простоты, я могу использовать эту функцию, чтобы найти самый высокий простой множитель

---

private static long HighestPrimeFactor(long input)
{
    bool searching = true;
    long highestFactor = 0;
    while (searching)
    {
        long factor = IsPrime(input);
        if (factor != -1)
        {
            theFactors.Add(factor);
            input = input / factor; 
        }
        if (factor == -1)
        {
            theFactors.Add(input);
            highestFactor = theFactors.Max();
            searching = false;
        }
    }
    return highestFactor;
}

Надеюсь, это поможет, не отдавая слишком много.