Словарь простых чисел

Question

Я пытался создать эту вспомогательную функцию в C #, которая возвращает первые n простых чисел. Я решил хранить цифры в словаре в формате <int,bool>. Ключом является число, о котором идет речь, и значение bool представляет, является ли int простым или нет. Существует масса ресурсов для вычисления / генерации простых чисел (включая SO), поэтому я подумал о том, чтобы объединить массы, создав еще один простой генератор простых чисел.

Моя логика выглядит следующим образом:

public static Dictionary<int,bool> GetAllPrimes(int number)
    {
        Dictionary<int, bool> numberArray = new Dictionary<int, bool>();


        int current = 2;
        while (current <= number)
        {
            //If current has not been marked as prime in previous iterations,mark it as prime
            if (!numberArray.ContainsKey(current))
                numberArray.Add(current, true);

            int i = 2;
            while (current * i <= number)
            {
                if (!numberArray.ContainsKey(current * i))
                    numberArray.Add(current * i, false);
                else if (numberArray[current * i])//current*i cannot be a prime
                    numberArray[current * i] = false;
                i++;

            }
            current++;
        }
        return numberArray;
    }

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

Answer 1

Для хранения целых чисел явно требуется не менее 32 бит на простое число, с некоторыми издержками для структуры контейнера.

При 2 ³¹ максимальное значение, которое может принять 32-разрядное целое число со знакомпримерно каждое 21,5-е число простое.Меньшие простые числа являются более плотными, число 1 в ln (n) чисел простое вокруг n.

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

Кажется, это называется BitArray в C # (в Java это BitSet).

Answer 2

Во-первых, вам нужно только зациклить, пока квадратный корень из числа.Сделайте все числа ложными по умолчанию и установите простой флаг, который вы устанавливаете в начале каждой итерации.

Кроме того, не храните его в словаре.Сделайте это массивом bool, и индекс должен быть числом, которое вы ищете.Только 0 не имеет никакого смысла, но это не имеет значения.Вы не должны инициировать либо;bools ложные по умолчанию.Просто объявите bool[] из number длины.

Затем я начну так:

primes[2] = true;
for(int i = 3; i < sqrtNumber; i += 2) {

}

Таким образом, вы автоматически пропустите все четные числа.Кстати, никогда не объявляйте переменную (i) в цикле, это замедляет ее.

Вот и все.Для получения дополнительной информации см. на этой странице.

Answer 3

Первое, что беспокоит, это то, почему вы храните само число?

Разве вы не можете просто использовать сам индекс, который будет представлять число?

PS: I 'Я не ac # developer, так что, возможно, это невозможно с помощью словаря, но это может быть сделано с соответствующей структурой.

Answer 4

Словарь действительно не имеет здесь смысла - просто сохраняйте все простые числа до заданного числа в списке.Затем выполните следующие действия:

Is given number in the list?  
    Yes - it's prime.  Done.
Not in list
Is given number larger than the list maximum?
    No - it's not prime.  Done.
Bigger than maximum; need to fill list up to maximum.
Run a sieve up to given number.
Repeat.

Answer 5

1) С точки зрения клиента для этой функции, не было бы лучше, если бы возвращаемый тип был bool [] (возможно, от 0 до number)? Внутри у вас есть три состояния (KnownPrime, KnownComposite, Unknown), которые могут быть представлены перечислением. Внутреннее хранение массива этого перечисления, предварительно заполненного Unknown, будет быстрее, чем словарь.

2) Если вы придерживаетесь словаря, часть решета, которая помечает кратные значения текущего числа как составные, может быть заменена шаблоном numberArray.TryGetValue(), а не многократными проверками для ContainsKey и последующим извлечением значения с помощью ключ.

Answer 6

Я почти уверен, что Dictionary на самом деле ухудшает производительность , поскольку она не позволяет вам выполнить пробные деления в оптимальном порядке. Традиционно вы должны хранить известные простые числа, чтобы их можно было перебирать от наименьшего к наибольшему, поскольку меньшие простые числа являются факторами более составных чисел, чем большие простые числа. Кроме того, вам никогда не нужно пытаться делить с любым простым числом, большим, чем квадратный корень из простого кандидата.

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

Answer 7

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

Как насчет использования метода, такого как:

bool IsPrime(int primeTest);

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