C# программа зависает в списке целых чисел

Question

Когда я запускаю свою программу, она доходит до того, что я инициализирую список целых чисел, и он замирает. Я знаю это, потому что Console.WriteLine(); методы после инициализации списка не отображаются на консоли. Когда я запускаю его, единственным выходом является "перед списком". Что мне не хватает? Я действительно надеюсь, что это не очевидно и не стыдно.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Euler._1_50
{
    class Challenge3
    {
        public Challenge3()
        {
            Console.WriteLine("before list");

            long num = 600_851_475_143;
            long high = 0;
            long length = 0;
            List<int> factr = new List<int>();

            Console.WriteLine(IsPrime(num));
            Console.WriteLine("after list");

            for (long i = 2; i <= num / 2; i++)
            {
                if (IsPrime(i) && num / i == 0)
                {
                    num = num / i;
                    factr.Add((int)i);
                    length++;
                }
            }

            for (long i = 0; i <= length; i++)
            {
                if (i > high) high = i;
            }

            Console.WriteLine(high);

        }

        private bool IsPrime(long i)
        {
            bool isPrime = false;

            for (long j = 2; j <= i/2; j++)
            {
                if (i % j == 0) isPrime = false;
                else isPrime = true;
            }
            return isPrime;
        }
    }
}

Answer 1

Так что я занимаюсь вопросами проекта Эйлера. Мне удалось создать алгоритм поиска простого допинга за день до того, как я это сделал, но мне было лень вникнуть в главный вопрос факторинга, рассмотренный в первом посте. После очередного дня отказа от поиска ответов и ненависти к жизни я наконец-то написал лучшую программу. Теперь я могу найти ответ примерно через полсекунды. Возможно, может быть чище, но это сделано, что мне нужно, чтобы сделать. #sosatisfying

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Euler._1_50
{
    class Challenge3_1
    {
        List<long> primes = new List<long>();
        List<bool> isPrime = new List<bool>();
        List<int> factors = new List<int>();

        long primeNums = 0;
        long bigNum = 600_851_475_143;
        int primeBnds = 1_000_000;

        public Challenge3_1()
        {
            genList();
            getPrimes();
            //listPrimes();
            factor();

            Console.WriteLine("final");
            listFactors();
        }


        //not currently being used
        private void genList()
        {
            for (int i = 0; i <= primeBnds; i++)
            {
                isPrime.Add(true);
            }
        }

        private void getPrimes()
        {
            isPrime[0] = false;
            isPrime[1] = false;

            for (int i = 2; i <= primeBnds; i++)
            {
                if (isPrime[i] == true)
                {
                    for (int j = i, index = 0; index <= primeBnds; index += j)
                    {
                        if (j < index)
                        {
                            isPrime[index] = false;
                        }
                    }
                }
            }
        }

        private void factor()
        {
            long temp = bigNum;

            for (int i = 2; i <= primeBnds;)
            {
                if (isPrime[i] == true && temp % i == 0)
                {
                    temp = temp / i;
                    factors.Add(i);
                    Console.WriteLine(i);
                }

                if (temp % i != 0)
                {
                    i++;
                }

                //if (factors.Capacity != 0) listFactors();
            }

        }

        private void listPrimes()
        {
            for (int i = 0; i <= primeBnds; i++)
            {
                if (isPrime[i] == true)
                {
                    Console.WriteLine(++primeNums + " " + i);
                }
            }
        }

        private void listFactors()
        {
            for (int i = 0; i < factors.Capacity; i++)
            {
                Console.Write(factors[i] + " ");
            }
        }

    }
}

Answer 2

IsPrime будет выполнять не менее 300 миллиардов итераций, поэтому он блокируется.

Основные факторы целого числа никогда не будут больше, чем квадратный корень из этого целого числа.

Кроме того, после того как вы определили число как простое, вам не нужно продолжать проверять.

Так что подумайте об изменении цикла теста на:

private bool IsPrime(long i)
{
    long upper = (long)Math.Sqrt(i);
    for (long j = 2; j <= upper; j++)
    {
        if (i % j == 0)
           return false;
    }
    return true;
}

Наконец, последний кусок кода о 'high' предполагает, что вы намереваетесь использовать это в большем куске кода. Если это так, лучше предварительно рассчитать, какие числа являются простыми числами, и сохранить их в List или HashSet для быстрого повторного использования.

Answer 3

Это не List<T> конструктор, который висит Это IsPrime называется с 600_851_475_143 в качестве аргумента. С циклом, работающим вдвое, это 300 миллиардов итераций. Это займет время.

И даже если вы ждете, пока он вернется, следующий цикл запускается IsPrime для всех целых чисел от 2 до тех же 300 миллиардов. Для этого потребуется еще больше времени. Требуется более 90 триллионов итераций самого внутреннего цикла!

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