检查数字是否是最好的algorithm最好的algorithm是什么?

可能重复:
素数的高效存储

只是我正在寻找的一个例子:我可以表示每一个奇数,例如对于给定的数字范围(1,10),从3开始:

1110 

下面的字典可以挤得更正确吗? 我可以用一些工作来重复5的倍数,但是以1,3,7或9结尾的数字必须在这个位数中。 希望这会澄清我想要的。

我正在寻找最好的algorithm,检查一个数是否是质数,即布尔函数:

 bool isprime(number); 

我想知道实现此function的最佳algorithm。 当然,会有我可以查询的数据结构。 我定义了最好的algorithm ,作为在范围(1,N)内产生一个具有最低内存消耗的数据结构的algorithm,其中N是一个常数。

素数testing有很多种方法。

没有真正的数据结构供您查询。 如果你有很多数字要testing,那么你应该运行一个概率testing,因为速度更快,然后用确定性testing来确定数字是否是最好的。

你应该知道,最快algorithm背后的math不适合心脏病。

通用的主要testing最快的algorithm是AKS 。 维基百科的文章在篇幅和链接上对原文进行了描述。

如果你想find大数字,看看像梅森素数特殊forms的素数 。

我通常实现的algorithm(易于理解和代码)如下(在Python中):

 def isprime(n): """Returns True if n is prime.""" if n == 2: return True if n == 3: return True if n % 2 == 0: return False if n % 3 == 0: return False i = 5 w = 2 while i * i <= n: if n % i == 0: return False i += w w = 6 - w return True 

这是经典的O(sqrt(N))algorithm的变体。 它使用一个素数(2和3除外)是6k - 16k + 1forms的事实,只看这种forms的除数。

有时,如果我真的想要速度, 范围是有限的 ,我执行基于费马小定理的伪总理testing。 如果我真的想要更多的速度(即完全避免O(sqrt(N))algorithm),我预先计算误报(请参阅Carmichaels数字)并进行二分search。 这是迄今为止我所实现的最快的testing,唯一的缺点是范围有限。

在我看来,最好的方法就是使用以前的东西。

有互联网上的第一个N素数列表, N伸展至less五千万 。 下载这些文件并使用它们,可能会比其他任何方法快得多。

如果你想要一个真正的algorithm来制作自己的素数,维基百科在这里有各种各样的优质素材,包括各种方法的链接和这里的主要testing,基于概率和快速确定的方法。

应该有一致的努力,find第一个十亿(甚至更多)素数,并让他们在networking上发表,这样人们可以停止做同样的工作,一遍又一遍,… 🙂

根据维基百科的说法,Eratosthenes的Sieve的 复杂度是O(n * (log n) * (log log n))并且需要O(n)记忆 – 所以如果你没有testing特别大数字。

 bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n%2 == 0 || n%3 == 0) return false; for (int i=5; i*i<=n; i=i+6) if (n%i == 0 || n%(i+2) == 0) return false; return true; } this is just c++ implementation of above AKS algorithm 

https://en.wikipedia.org/wiki/AKS_primality_test

最小的记忆? 这不是最小的,而是朝着正确的方向迈出的一步。

 class PrimeDictionary { BitArray bits; public PrimeDictionary(int n) { bits = new BitArray(n + 1); for (int i = 0; 2 * i + 3 <= n; i++) { bits.Set(i, CheckPrimality(2 * i + 3)); } } public PrimeDictionary(IEnumerable<int> primes) { bits = new BitArray(primes.Max()); foreach(var prime in primes.Where(p => p != 2)) { bits.Set((prime - 3) / 2, true); } } public bool IsPrime(int k) { if (k == 2) { return true; } if (k % 2 == 0) { return false; } return bits[(k - 3) / 2]; } } 

当然,你必须指定CheckPrimality的定义。

Python 3:

 def is_prime(a): return a > 1 and all(a % i for i in range(2, int(a**0.5) + 1)) 

我认为最快的是我做的方法。

 void prime(long long int number) { // Establishing Variables long long int i = 5; int w = 2; const long long int lim = sqrt(number); // Gets 2 and 3 out of the way if (number == 1) { cout << number << " is hard to classify. \n"; return; } if (number == 2) { cout << number << " is Prime. \n"; return; } if (number == 3) { cout << number << " is Prime. \n"; return; } // Tests Odd Ball Factors if (number % 2 == 0) { cout << number << " is not Prime. \n"; return; } if (number % 3 == 0) { cout << number << " is not Prime. \n"; return; } while (i <= lim) { if (number % i == 0) { cout << number << " is not Prime. \n"; return; } // Tests Number i = i + w; // Increments number w = 6 - i; // We already tested 2 and 3 // So this removes testing multepules of this } cout << number << " is Prime. \n"; return; } 

与已经提到的AKSalgorithm类似的想法

 public static boolean isPrime(int n) { if(n == 2 || n == 3) return true; if((n & 1 ) == 0 || n % 3 == 0) return false; int limit = (int)Math.sqrt(n) + 1; for(int i = 5, w = 2; i <= limit; i += w, w = 6 - w) { if(n % i == 0) return false; numChecks++; } return true; } 

你可以试试这个代码:

 def isprime(n): if n == 1: return False for i in range(2,int(n**0.5)+1): if n%i==0: return False return True 

要使用它,只需键入isprime(NUMBER)

使用此代码,您可以询问用户的号码,并检查它是否是主要的:

 def isprime(n): if n == 1: return False for i in range(2,int(n**0.5)+1): if n%i==0: return False return True while True: number = input('Please Enter A Number: ') if isprime(int(number)): print('The Number You Entered Is A Prime Number', end='\n\n') else: print('The Number You Entered Is Not A Prime Number', end='\n\n')