检查数字是否是最好的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 - 1或6k + 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
最小的记忆？ 这不是最小的，而是朝着正确的方向迈出的一步。
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')
