返回范围[a，b]中所有质数的计数，使得所有数字都来自集合{1,5,9}。1<=a<=b<=10⁹

Question

返回a，b范围内所有质数的计数，使得所有数字都来自集合{1,5,9}。1<=a<=b<=10⁹。

我的方法-我试图生成集合{1,5,9}中的所有数字。结果是3^9(19683)，之后我检查它是否是质数。

我能用更好的时间复杂度来做这件事吗？

Answer 1

1. 从不生成大集合，并在检查集合的所有元素后，排除大多数元素。这需要大量的内存来存储你将要丢弃的东西。取而代之的是，找到具有“有效”数字的单个数字，检查素数，然后将其存储在一个集合中。与做数学相比，在现代计算机上访问大型内存数组非常耗时。
2. “我生成了所有的数字”：我希望你做得很聪明！例如，您永远不需要检查最后一位数是5的数字作为素数(只有一个素数以5结尾；那就是5本身！)。此外，您希望不要“手动”构建所有的数字组合。比方说，你找到了一个19551的数字，那么19559也是一个候选数字，你永远不需要手动“组合”数字来尝试最后一个数字。
3. 当然，你的质数检查算法需要与你的问题相匹配:例如，你可以删除初始的2整除检查(你永远不会产生偶数)。你永远不需要检查5的整除性，因为你永远不会使用5或0作为最后一个数字。根据您的主要检查算法，您可能还希望保存“杀死”xxxx1的因素--这是您不必检查xxxx9的一个因素。根据你的数字中的1,5和9的计数进行三因数检查；你可以直接从中推断出交叉和，因此是3整除。