Skip to content

01.10.2011

3

Задача №3 – projecteuler.net

Решил 3 задачу! Некоторые строчки кода писал чуть ли не интуитивно, но все таки программа выдала правильный результат. При чем выполнилась довольно быстро (я ушел от своего метода перебора=)).  Условие:

Простые делители числа 13195 — это 5, 7, 13 и 29.

Какой самый большой делитель числа 600851475143, являющийся простым числом?


Мое решение: с помощью решета Эратосфена находим все простые числа которые меньше sqrt(600851475143) — получаем массив в котором индексы — числа, а значение «true» или «false» показывают простое ли это число.

        static bool[] Prost(int n) // метод для нахождения простых чисел с помощью решета Эратосфена
        {
            bool[] m = new bool[n+1];
            for (int i = 2; i <= n; ++i)
            {
                if (m[i] == false)
                {
                    for (int j = 1; i + i * j <= n; ++j)
                    {
                        m[i + i * j] = true;
                    }
                }
            }
            return m;
        }

Получаем массив, в котором индексы элементов «false» соответствуют простым числам.
Далее осталось найти первое простое число-делитель с конца массива. Длина массива — корень из 600851475143. Окончательный код решения (обновлен) :

        static bool[] Prost(int n) // метод для нахождения простых чисел с помощью решета Эратосфена
        {
            bool[] m = new bool[n+1];
            for (int i = 2; i <= n; ++i)
            {
                if (m[i] == false)
                {
                    for (int j = 1; i + i * j <= n; ++j)
                    {
                        m[i + i * j] = true;
                    }
                }
            }
            return m;
        }
        static void Main(string[] args)
        {
            {
                int n = Convert.ToInt32(Math.Floor((Math.Sqrt(600851475143))));
                bool[] m = Prost(n);
                long ans = 2;
                for (int i = n; i > 2; --i)
                {
                    if ((m[i] == false) && 600851475143 % i == 0)
                    {
                        ans = i;
                        break;
                    }
                }
                Console.WriteLine(ans);
                Console.ReadKey();
            }
        }

Вот правильное (я почти уверен=)) решение:

        static long simple(long n)
        {
            long otv = 1;
            for (long i = 2; n > 1; i++)
            {
                if (n % i == 0)
                {
                    n /= i;
                    otv = i;
                    while (n % i == 0)
                    {
                        n /= i;
                    }
                }

            }
            return otv;
        }

Прикол в том, что мне удалось получить правильный ответ с помощью двух неправильных решений…
Число могли и получше придумать =).

3 Comments Post a comment
  1. Joy
    Окт 1 2011

    Мда, пример того, как неправильная программа дает правильный ответ.
    Да и «длинна» неправильно написано.

    Ответить
    • Окт 1 2011

      Теперь правильная?

      Ответить
      • Joy
        Окт 1 2011

        Ну представь себе, что заданное число является произведением какого-то большого простого числа и, скажем, 2,
        N = 2 * P.
        Разве твоя программа найдет P?

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments