Как я могу найти простые числа с помощью битовых операций в C ++?

Question

Как найти простые числа с помощью битовых операций в C ++?

Answer 1

Я думаю, что способ сделать это - не думать о наборе битов как о его числовом представлении, как мы обычно это делаем, а думать об этом в виде списка чисел. Итак, битсет

1111

будет представлять числа 1, 2, 3 и 4. Теперь, если мы скажем, что «1» представляет простое число, а «0» представляет не простое число, мы можем сделать сито следующим образом.

Установите все биты в 1 (я собираюсь использовать 16 битов, которые представляют целые числа от 1 до 16)

1111 1111 1111 1111

Я знаю, что это не простое число, поэтому я устанавливаю его на ноль.

0111 1111 1111 1111

Теперь я знаю, что следующая «1», с которой я сталкиваюсь, представляет собой простое число, но все кратные этому числу по определению не простые, поэтому я оставляю следующую «1» одну, но устанавливаю все из его кратных 0. Поскольку следующий «1» представляет число 2, я обнуляю каждый второй бит.

0110 1010 1010 1010

Преимущество этого метода перед другими заключается в том, что когда я пересекаю остальные биты, мне не нужно проверять каждый из них, чтобы увидеть, делится ли он на 2 (поэтому ничего подобного if i % 2 == 0 не требуется). Я могу просто продолжать увеличивать индекс на 2, и я знаю, что всегда буду попадать на не простое число.

Теперь я просто делаю то же самое снова со следующей '1', с которой я сталкиваюсь (следующее простое число, начинающееся с последнего идентифицированного мной простого числа, 2). Я знаю, что это простое число, так как оно не делится ни на одно из чисел под ним. Я знаю, что все его кратные являются простыми, поэтому, поскольку он находится в третьей позиции, я устанавливаю каждый третий следующий бит в «0». Некоторые из них уже равны «0», поскольку они также кратны 2. Это нормально, просто оставьте их «0».

0110 1010 0010 1000

Следующее «1», с которым вы сталкиваетесь, является пятым битом. Теперь вы могли бы продолжать работу, пока не дойдете до конца, но, поскольку 5 больше квадратного корня из числа битов, с которого я начал, я знаю, что больше не найду никаких композитов, поэтому Я сделал.

<ч />

После небольшого поиска я нашел действительно хороший пример реализации в C ++ Как программировать в Deitel & Deitel. Они также дают хорошие объяснения алгоритма и кода.

Answer 2

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

Answer 3

Если вы не знаете, то получение ответа от кого-то другого - это обман, не так ли? Скажи парню, которого не знаешь. Это нормально, чтобы не знать каждый вопрос в интервью. Выглядит гораздо хуже, когда вас ловят на мошенничестве или копировании, чем на словах «я не знаю». Объясните, как вы знаете, что такое простое число, объясните некоторые свойства простых чисел и объясните, что вы знаете о битовых операциях. Если вы не знаете этих вещей, то, возможно, эта работа не для вас?

Answer 4

Я нашел этот код C #, я уверен, что вы можете прочитать его хорошо.

using System;
using System.Collections.Generic;
using System.Text;

namespace eratosthenes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 100;
            bool[] primes = new bool[n];
            for (int i = 2; i < n; i++) {
                primes[i]=true;
            }

            for (int i = 2; i < n; i++) {
                if (primes[i] == true) {
                    for (int j = i * i; j < n; j=j+i)
                    {
                        primes[j] = false;
                    }
                    Console.WriteLine(i);
                }
            }
            Console.ReadLine();
        }
    }
}

Ссылка на страницу немецких викибукс .