一位同事刚刚告诉我,由于与散列相关的神秘原因,C#字典集合根据质数调整大小。我直接的问题是,“它怎么知道下一个素数是什么?他们是在讲一个巨大的表还是在飞行中计算?这是一个可怕的非确定性运行时插入导致调整大小。”
所以我的问题是,给定N,这是一个质数,计算下一个质数的最有效方法是什么?
发布于 2010-12-18 09:07:12
众所周知,gaps between consecutive prime numbers非常小,质数370261出现了第一个超过100%的差距。这意味着即使是一个简单的蛮力在大多数情况下也足够快,平均需要O(ln(p)*sqrt(p))。
对于p=10,000,这是O(921)操作。请记住,我们将在每次O(ln(p))插入(粗略地说)时执行一次,这完全符合大多数现代硬件上毫秒量级的大多数问题的约束。
发布于 2010-12-18 09:17:14
以防有人好奇:
使用reflector I确定.Net使用一个静态类,它包含一个硬编码的~72个素数列表,范围最大为7199369,它扫描至少是当前大小的两倍的最小素数,对于大于当前大小的最小素数,它通过尝试除以所有奇数直到潜在数的sqrt来计算下一个素数。这个类是不可变的,并且是线程安全的(即较大的素数不会被存储起来以备将来使用)。
发布于 2010-12-18 10:32:28
一个很好的技巧是使用部分筛子。例如,数字N= 2534536543556后面的下一个质数是什么?
检查N相对于一列小素数的模数。因此...
mod(2534536543556,[3 5 7 11 13 17 19 23 29 31 37])
ans =
2 1 3 6 4 1 3 4 22 16 25
我们知道N后面的下一个素数必须是奇数,并且我们可以立即丢弃这个小素数列表中的所有奇数倍。这些模使我们可以筛选出那些小素数的倍数。如果我们使用小于200的小素数,我们可以使用这个方案立即丢弃大多数大于N的潜在素数,除了一个小列表。
更明确地说,如果我们寻找一个超过2534536543556的质数,它不能被2整除,所以我们只需要考虑超过这个值的奇数。上面的模数表明,2534536543556与2 mod 3相同,因此2534536543556+1与0 mod 3相同,这必须是2534536543556+7,2534536543556+13等。有效地,我们可以筛选出许多数字,而不需要测试它们的素性,也不需要任何试除法。
类似地,事实是
mod(2534536543556,7) = 3
告诉我们2534536543556+4与0mod7同余。当然,这个数字是偶数,所以我们可以忽略它。但是2534536543556+11是一个可以被7整除的奇数,2534536543556+25也是如此。同样,我们可以清楚地将这些数字排除在外(因为它们可以被7整除),因此不是素数。
只使用最多37个素数的小列表,我们可以排除紧跟在起点2534536543556之后的大多数数字,只有几个除外:
{2534536543573 , 2534536543579 , 2534536543597}
在这些数字中,它们是质数吗?
2534536543573 = 1430239 * 1772107
2534536543579 = 99833 * 25387763
我已经尽力提供了列表中前两个数字的素数分解。注意它们是复合的,但主因子很大。当然,这是有道理的,因为我们已经确保了剩余的数字都不能有小的素数因子。我们的短列表中的第三个(2534536543597)实际上是N之外的第一个素数。我描述的筛选方案往往会导致数字要么是素数,要么是由通常较大的素数因子组成。因此,在找到下一个素数之前,我们实际上只需要对几个数字应用显式质数测试。
类似的方案很快就会产生超过N= 1000000000000000000000000000的下一个素数,如100000000000000000000000000103。
https://stackoverflow.com/questions/4475996
复制相似问题