使用$ P $埃拉托色尼筛pcalculated素数 [英] Sieve of Eratosthenes using precalculated primes
问题描述
我已经可以存储32位的所有质数无符号整型和我想用它来生成一些64位的素数。使用审判庭太慢，即使在逻辑上和编译优化。
I've all prime numbers that can be stored in 32bit unsigned int and I want to use them to generate some 64bit prime numbers. using trial division is too slow even with optimizations in logic and compilation.
我想修改的埃拉托色尼筛与predefined名单的工作，如下：
I'm trying to modify Sieve of Eratosthenes to work with the predefined list, as follow:
- 在数组A从2到4294967291
- 在数组b从2 ^ 32至X INC 1
- 找到C的是现任总理的第一次多。
- 从C标志，并通过跳跃现任总理到的X.
- 去1。
现在的问题是步骤3，使用模寻找黄金多，这样的操作是，我没有使用跟踪分裂的原因。
The problem is step 3 which use modulus to find the prime multiple, such operation is the reason i didn't use trail division.
有没有什么更好的方法来实施步骤3或整个算法。
Is there any better way to implement step 3 or the whole algorithm.
感谢你。
推荐答案
增量为2，而不是1。这是最小的优化，你应该总是使用 - 只赔率工作。无需费心的唇上。
Increment by 2, not 1. That's the minimal optimization you should always use - working with odds only. No need to bother with the evens.
在C ++中，使用矢量＆lt;布尔＆GT; 的筛阵列。它就会自动位包装。
In C++, use vector<bool> for the sieve array. It gets automatically bit-packed.
pre-计算核心的素数与分段筛。然后继续用足够大的部分是适合你的缓存工作，而无需添加新的素数到核心清单。对于每一个主要的 P 的维护额外的很长很长的int值：当前多（从开始黄金广场，当然，）。步骤值的两次 P 的价值，或 P 赔率包装筛数组，其中的 我 的-th条目代表数量的 0偏移+ 2I 的 0 的是最不奇不低于量程开始。无需由倍数进行排序'值，上界核心的素数利用单调上升。
Pre-calculate your core primes with segmented sieve. Then continue to work by big enough segments that fit in your cache, without adding new primes to the core list. For each prime p maintain additional long long int value: its current multiple (starting from the prime's square, of course). The step value is twice p in value, or p offset in the odds-packed sieve array, where the i-th entry stands for the number o + 2i, o being the least odd not below the range start. No need to sort by the multiples' values, the upper bound of core primes' use rises monotonically.
的sqrt（0xFFFFFFFFFF） = 1048576 。 PrimePi（1048576）= 82025 素数是所有你需要在你的核心素数表。这是花生。
sqrt(0xFFFFFFFFFF) = 1048576. PrimePi(1048576)=82025 primes is all you need in your core primes list. That's peanuts.
整数算术的得到long long int 取值应该工作得很好找模，等最小的倍数范围内，当你第一次启动（或恢复工作）
Integer arithmetics for long long ints should work just fine to find the modulo, and so the smallest multiple in range, when you first start (or resume your work).
另请参阅相关的伪code 回答，的另一个为C code 。
See also a related answer with pseudocode, and another with C code.
这篇关于使用$ P $埃拉托色尼筛pcalculated素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
