mjv*_*mjv 18
给定相对较小的目标范围,而不是排序的素数列表,有一个数组由该范围内的所有奇数索引(你知道除了特殊情况2之外没有偶数素数)并且包含最接近的素数.找到解决方案成为O(1)时间.
我认为第100个素数大约是541个.需要270个[小]整数的数组.
考虑到素数的相对高密度(特别是相对于奇数),在1,000以下的范围内,这种方法特别有效.(因为这会影响二叉树的大小)
Jer*_*fin 11
如果您只需要搜索前100个素数,那么只需创建这些素数的有序表,然后进行二分搜索.这将使您获得一个素数,或两个之间的点,并检查哪一个更接近.
编辑:考虑到该范围内素数的分布,您可以通过使用插值搜索来加快速度(一点点) - 而不是始终从表格的中间开始,使用线性插值来猜测更准确的起点点.第100个素数应该在250左右左右(猜测 - 我没有检查过),所以如果(例如)你想要一个最接近50的那个,那么你将开始大约1/5到达数组而不是中途.您可以将素数视为从1开始,因此只需将您想要的数字除以您范围内的最大值即可猜测起点.