在给定数字后找到素数 [英] Finding a prime number after a given number

问题描述

如何找到大于给定数字的最小素数？例如，给定4，我需要5；给定7，我需要11。

How can I find the least prime number greater than a given number? For example, given 4, I need 5; given 7, I need 11.

我想知道一些有关最佳算法的想法。我想到的一种方法是通过Eratosthenes筛子生成素数，然后在给定数之后找到素数。

I would like to know some ideas on best algorithms to do this. One method that I thought of was generate primes numbers through the Sieve of Eratosthenes, and then find the prime after the given number.

推荐答案

已经提出了其他一些方法，我认为它们是好的，但这实际上取决于您要在现场存储或计算的数量。例如，如果您要查找数量很大的下一个素数，则由于需要存储位数，因此使用Eratosthenes筛子可能不会那么好。

Some other methods have been suggested and I think that they are good, but it really depends on how much you want to have to store or compute on the spot. For instance if you are looking for the next prime after a very large number, then using the Sieve of Eratosthenes might not be so great because of the number of bits you would need to store.

或者，您可以检查大于输入数字的每个数字奇数N（包括3）和sqrt（N）之间的所有奇数整数，直到找到正确的数字为止数。当然，您可以在发现复合材料时停止检查。

Alternatively, you could check all odd integers between (and including) 3 and sqrt(N) on every number odd number N greater than the input number until you find the correct number. Of course you can stop checking when you find it is composite.

如果您想使用其他方法，则建议使用 1）的所有奇数进行％93Rabin_primality_test rel = noillerr>>米勒-拉宾素数测试，直到找到素数为止。如果遵循页面底部的列表，该列表的数字为 a 以检查给定的范围，则可以大大减少<$ c $的数量c> a s您需要检查。当然，在使用Miller-Rabin进行检查之前，您可能希望至少检查一些较小的素数（例如3、5、7、11）。

If you want a different method, then I would suggest using the Miller-Rabin primality test on all odd numbers above the input number (assuming the input is > 1) until a prime is found. If you follow the list, located at the bottom of the page, of numbers a to check for the given ranges, you can significantly cut down on the number of as you need to check. Of course, you might want to check at least a few of the smaller primes (3,5,7,11 for instance) before checking with Miller-Rabin.

这篇关于在给定数字后找到素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！