如何找到最近的素数？ [英] How do I find the nearest prime number?

问题描述

有没有什么好的算法来找到最近的素数给定的真正多少？我只需要在第一个素数100左右的时间内搜索。

Is there any nice algorithm to find the nearest prime number to a given real number? I only need to search within the first 100 primes or so.

在present，我有一堆存储在数组中的素数的和我检查的差别一个数字的时间（O（n）的？）。

At present, I've a bunch of prime numbers stored in an array and I'm checking the difference one number at a time (O(n)?).

推荐答案

而不是素数的排序列表，考虑到相对较小的范围内针对性的，必须由所有奇数范围内的索引的数组（你知道有没有甚至素数除2的特殊情况下），并包含最接近的素数。寻找解决方法变为O（1）时间上的。

Rather than a sorted list of primes, given the relatively small range targetted, have an array indexed by all the odd numbers in the range (you know there are no even primes except the special case of 2) and containing the closest prime. Finding the solution becomes O(1) time-wise.

我觉得100主要是大约541 270 [小]整数数组的所有需要​​。

I think the 100th prime is circa 541. an array of 270 [small] ints is all that is needed.

此方法特别有效，由于相对高密度的素数的（特别是相对于奇数），在低于1000的范围内。 （由于这会影响一二进制树的大小）

This approach is particularly valid, given the relative high density of primes (in particular relative to odd numbers), in the range below 1,000. (As this affects the size of a binary tree)

这篇关于如何找到最近的素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！