有没有什么好的算法可以找到最接近给定数字的素real
数?我只需要在前 100 个素数左右进行搜索。
目前,我有一堆素数存储在一个数组中,我一次检查一个数字的差异(O(n)?)。
考虑到目标范围相对较小,而不是排序的素数列表,而是有一个由该范围内的所有奇数索引的数组(您知道除了 2 的特殊情况之外没有偶数素数)并包含最接近的素数。找到解决方案在时间上变得 O(1)。
我认为第 100 个素数大约是 541。只需要 270 个 [小] 整数的数组。
考虑到素数的相对高密度(特别是相对于奇数),这种方法特别有效,在 1,000 以下的范围内。(因为这会影响二叉树的大小)
如果您只需要搜索前 100 个左右的素数,只需创建这些素数的排序表,然后进行二分搜索。这会让你得到一个素数,或者两个之间的一个点,然后你检查哪个更接近。
编辑:鉴于素数在该范围内的分布,您可能可以通过使用插值搜索来加快速度(一点点)——而不是总是从表格的中间开始,而是使用线性插值来猜测更准确的开始观点。第 100 个素数应该在 250 左右(猜测——我没有检查过),所以如果(例如)你想要最接近 50 的那个,你会从大约 1/5 开始数组而不是中途。您几乎可以将素数视为从 1 开始,因此只需将您想要的数字除以您范围内的最大值即可猜测起点。
鉴于手头的任务,到目前为止的答案相当复杂。前一百个素数都小于 600。我将创建一个大小为 600 的数组,并在每个数组中放置与该数字最接近的素数的值。floor
然后,给定一个要测试的数字,我会使用and函数将其上下四舍五入,ceil
以获得一两个候选答案。与这些数字的距离进行简单比较会给你一个非常快速的答案。
最快的算法?创建一个包含 p[100]=541 个元素的查找表并返回 floor(x) 的结果,其中 x 在 [2,3] 上的特殊逻辑。那将是O(1)。
最简单的方法是将素数存储在排序列表中并修改您的算法以进行二进制搜索。
标准的二分搜索算法将返回 null 以表示未命中,但为了您的目的应该直接对其进行修改。
您应该在数组中对您的号码进行排序,然后您可以使用二分搜索。该算法在最坏情况下的性能为 O(log n)。
<?php
$N1Diff = null;
$N2Diff = null;
$n1 = null;
$n2 = null;
$number = 16;
function isPrime($x) {
for ($i = 2; $i < $x; $i++) {
if ($x % $i == 0) {
return false;
}
}
return true;
}
for ($j = $number; ; $j--) {
if( isPrime($j) ){
$N1Diff = abs($number - $j);
$n1 = $j;
break;
}
}
for ($j = $number; ; $j++) {
if( isPrime($j) ){
$N2Diff = abs($number - $j);
$n2 = $j;
break;
}
}
if($N1Diff < $N2Diff) {
echo $n1;
} else if ($N1Diff2 < $N1Diff ){
echo $n2;
}
public static boolean p(int n){
for(int i=3;i*i<=n;i+=2) {
if(n%i==0)
return false;
}
return n%2==0? false: true; }
public static void main(String args[]){
String n="0";
int x = Integer.parseInt(n);
int z=x;
int a=0;
int i=1;
while(!p(x)){
a = i*(int)Math.pow(-1, i);
i++;
x+=a;
}
System.out.println( (int) Math.abs(x-z));}
这是n> = 2。
在蟒蛇中:
>>> def nearest_prime(n):
incr = -1
multiplier = -1
count = 1
while True:
if prime(n):
return n
else:
n = n + incr
multiplier = multiplier * -1
count = count + 1
incr = multiplier * count
>>> nearest_prime(3)
3
>>> nearest_prime(4)
3
>>> nearest_prime(5)
5
>>> nearest_prime(6)
5
>>> nearest_prime(7)
7
>>> nearest_prime(8)
7
>>> nearest_prime(9)
7
>>> nearest_prime(10)
11
Lookup table whit size of 100 bytes; (unsigned chars) Round real number and use lookup table.
如果数组解决方案对您来说不是一个有效的解决方案(它是您的方案的最佳解决方案),您可以尝试下面的代码。在“2 或 3”的情况下,它将检查每个奇数远离起始值,直到找到一个素数。
static int NearestPrime(double original)
{
int above = (int)Math.Ceiling(original);
int below = (int)Math.Floor(original);
if (above <= 2)
{
return 2;
}
if (below == 2)
{
return (original - 2 < 0.5) ? 2 : 3;
}
if (below % 2 == 0) below -= 1;
if (above % 2 == 0) above += 1;
double diffBelow = double.MaxValue, diffAbove = double.MaxValue;
for (; ; above += 2, below -= 2)
{
if (IsPrime(below))
{
diffBelow = original - below;
}
if (IsPrime(above))
{
diffAbove = above - original;
}
if (diffAbove != double.MaxValue || diffBelow != double.MaxValue)
{
break;
}
}
//edit to your liking for midpoint cases (4.0, 6.0, 9.0, etc)
return (int) (diffAbove < diffBelow ? above : below);
}
static bool IsPrime(int p) //intentionally incomplete due to checks in NearestPrime
{
for (int i = 3; i < Math.Sqrt(p); i += 2)
{
if (p % i == 0)
return false;
}
return true;
}
也许我们可以找到左右最近的素数,然后比较得到最接近的素数。(我假设下一个素数出现在接下来的 10 次中)
def leftnearestprimeno(n):
n1 = n-1
while(n1 >= 0):
if isprime(n1):
return n1
else:
n1 -= 1
return -1
def rightnearestprimeno(n):
n1 = n+1
while(n1 < (n+10)):
if isprime(n1):
return n1
else:
n1 += 1
return -1
n = int(input())
a = leftnearestprimeno(n)
b = rightnearestprimeno(n)
if (n - a) < (b - n):
print("nearest: ", a)
elif (n - a) > (b - n):
print("nearest: ", b)
else:
print("nearest: ", a) #in case the difference is equal, choose min
#value
最简单的答案 - 每个素数都可以用(6*x-1 和 6*X +1)的形式表示(2 和 3 除外)。设数为 N. 除以 6。 t=N/6; 现在 a=(t-1)*6 b=(t+1)*6 并检查哪个更接近 N。