Почему моя программа для поиска наибольшего простого числа никогда не выполняет запись на консоль?

#c# #prime-factoring

#c# #разложение на простые множители

Вопрос:

Я отладил свой код, и все работает отлично. Но мой код по какой-то причине никогда не записывается на консоль.

Вот мой код:

   long largest = 0;


        for (long i = 1; i < 600851475144; i  )
        {
            long check = 0;
            for (long j = 1; j < i   1; j  )
            {

                if ((i%j) == 0)
                {
                    check  ;
                }
            }
            if (check == 2)
            {
                largest = i;
            }
        }

        Console.WriteLine(largest);
        Console.ReadKey();

Вопрос: Как мне записать на консоль?

1. Работает на dotnetfiddle (с уменьшенным счетчиком циклов для сокращения времени выполнения). Может быть, ваш код просто занимает огромное количество времени? Подумайте о том, чтобы печатать сообщения о состоянии каждые миллион чисел или около того, чтобы увидеть, что это действительно что-то делает.

2. Потому что у вас есть два вложенных цикла, которые выполняются большое количество времени. Поэтому вам приходится долго ждать, чтобы достичь WriteLine .

3. Я позволил ей работать целую минуту, все еще не получив ответа. Я попытаюсь уменьшить это. Посмотрим, сработает ли это.

4. Очень долгое, очень долгое время.

Ответ №1:

Ваш алгоритм слишком медленный, чтобы завершить его за разумное время, поэтому вам нужно придумать альтернативный подход.

Во-первых, алгоритм должен прекратить проверку наивного определения (два делителя). Если вы проверили все делители с точностью до квадратного корня из числа и не нашли ни одного, число является простым. Во-вторых, если вы ищете наибольшее простое число в диапазоне, начните с вершины диапазона, идите вниз и остановитесь, как только найдете первое простое число. В-третьих, нет смысла пробовать использовать четные числа.

Реализация этих трех изменений позволит запустить ваш алгоритм вовремя.

Ответ №2:

Что?

Это завершится, но это будет длиться вечно из-за всех итераций, которые она должна выполнить.

Вычисление нахождения простого числа — это очень трудоемкое вычисление, особенно в том виде, в каком вы это сделали.

Подводя итог, он не возвращается, потому что вам приходится ждать минуты / часы / дни / годы? Чтобы вычислить это.

Ответ №3:

Ваш алгоритм плох. Для этого приходится выполнять много итераций. Как уже упоминали другие, нет смысла делить на четные числа, поэтому увеличивайте на два, начните с 3, вы можете уменьшить количество итераций до квадратного корня из заданного числа. моя тоже не идеальна, но она завершается в мгновение ока. Идея состоит в том, чтобы уменьшить количество итераций путем деления заданного числа на все найденные делители. Попробуйте на свой страх и риск!

     long FindLargestPrimeDivisor(long number)
    {
        long largestPrimeDivisor = 1;
        while (true)
        {
            if (number % largestPrimeDivisor == 0)
            {
                number /= largestPrimeDivisor;
            }
            if (number < largestPrimeDivisor)
            {
                break;
            }
            largestPrimeDivisor  ;
        }
        return largestPrimeDivisor;
    }