c++ - 如何通过 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 大于我开始的位数的平方根，我知道我不会再找到任何复合了，所以我完成了。

---

After a little more searching I found a really good implementation example in Deitel & Deitel's C++ How to Program. They also provide good explanations of the algorithm and code.

Answer 2

尝试使用 bitset实现素筛。该算法只需要存储某个数是否为质数。一点就足够了。

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();
        }
    }
}

德语 wikibooks 页面的链接。