首页 文章

检查数字是否为素数的最佳算法是什么?

提问于
浏览
118

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

1110

以下字典可以挤得更对吗?我可以通过一些工作来消除五的倍数,但是以1,3或7或9结尾的数字必须存在于位数组中 . 希望这能澄清我想要的东西 .

我正在寻找最好的算法,检查数字是否为素数,即布尔函数:

bool isprime(number);

我想知道实现此功能的最佳算法 . 当然,我可以查询一个数据结构 . 我 define the best algorithm ,是为范围(1,N)产生具有最低内存消耗的数据结构的算法,其中N是常数 .

23 回答

  • 23

    有很多方法可以做primality test .

    您没有真正的数据结构可供查询 . 如果你有很多要测试的数字,你应该运行probabilistic test,因为它们更快,然后用deterministic test跟进它以确保数字是素数 .

    你应该知道最快算法背后的数学不适合胆小的人 .

  • 0

    一般素数测试的最快算法是AKS . 维基百科的文章描述了它的长度和原始论文的链接 .

    如果你想找到大数字,请查看具有特殊形式的素数,如Mersenne primes .

    我通常实现的算法(易于理解和编码)如下(在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)) 算法的变体 . 它使用这样一个事实:素数(除了2和3)的形式为 6k - 16k + 1 ,并且只看这种形式的除数 .

    有时,如果我真的想要速度并且范围有限,我实现了基于Fermat's little theorem的伪素数测试 . 如果我真的想要更快的速度(即完全避免O(sqrt(N))算法),我预先计算误报(参见Carmichael数字)并进行二分搜索 . 这是迄今为止我实施过的最快的测试,唯一的缺点是范围有限 .

  • 177

    在我看来,最好的方法是使用以前的方法 .

    互联网上有第一批 N 素数列表, N 至少延伸至fifty million . 下载文件并使用它们,'s likely to be much faster than any other method you' ll想出来 .

    如果你想要一个实际的算法来制作你自己的素数,维基百科在素数here上有各种好东西,包括各种方法的链接,以及主要测试here,基于概率和快速确定性方法 .

    应该齐心协力找到最初的十亿(甚至更多)素数并将它们发布到网上的某个地方,以便人们可以一次又一次地停止做同样的工作...... :-)

  • 1
    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

  • 6

    根据维基百科,the Sieve of Eratosthenescomplexity O(n * (log n) * (log log n)) and requires O(n) memory - 所以它测试特别大的数字 .

  • -1

    方太晚了,但希望这会有所帮助 . 如果您正在寻找大素数,这是相关的:

    要测试大的奇数,您需要使用Fermat测试和/或Miller-Rabin测试 .

    这些测试使用模幂运算,这是非常昂贵的,对于 n 位取幂,你至少需要 n 大int乘法和 n 大int divison . 这意味着模幂运算的复杂度为O(n³) .

    所以在使用大枪之前,你需要进行相当多的试验 . 但是不要天真地做,有办法快速做到这一点 . 首先将尽可能多的素数相乘,然后将许多素数组合成用于大整数的词 . 如果使用32位字,则乘以3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 3234846615,并使用欧几里德算法计算最大公约数 . 在第一步之后,数字减少到字大小以下并继续算法而不执行完整的大整数除法 . 如果GCD!= 1,这意味着你乘以的素数之一除以数字,所以你有一个证明它不是素数 . 然后继续31 * 37 * 41 * 43 * 47 = 95041567,依此类推 .

    一旦你以这种方式测试了几百(或千)个素数,你可以做40轮Miller-Rabin测试以确认数量是素数,经过40轮你可以肯定数量是素数只有2 ^ -80的机会它是不是(你的硬件更可能发生故障......) .

  • 1

    In Python 3:

    def is_prime(a):
        if a < 2:
            return False
        elif a!=2 and a % 2 == 0:
            return False
        else:
            return all (a % i for i in range(3, int(a**0.5)+1))
    

    Explanation: 素数是一个只能被1和1整除的数字 . 例如:2,3,5,7 ......

    1) if a<2: 如果"a"小于2则不是素数 .

    2) elif a!=2 and a % 2 == 0: 如果"a"可以被2整除,那么它绝对不是素数 . 但是如果a = 2,我们不想评估它,因为它是素数 . 因此条件a!= 2

    3) return all (a % i for i in range(3, int(a 0.5)1)):**首先看一下python中all()命令的作用 . 从3开始,我们将"a"除以它的平方根(a ** 0.5) . 如果"a"可被整除,则输出将为False . 为什么平方根?让's say a=16. The square root of 16 = 4. We don' t需要评估到15 . 我们只需要检查到4,说它不是素数 .

    Extra: 用于查找范围内所有素数的循环 .

    for i in range(1,100):
        if is_prime(i):
            print("{} is a prime number".format(i))
    
  • 7

    Python 3:

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

    我有一个功能,直到(2 ^ 61)-1这里:

    from math import sqrt
    def isprime(num): num > 1 and return all(num % x for x in range(2, int(sqrt(num)+1)))
    

    Explanation:

    all() 函数可以重新定义为:

    def all(variables):
        for element in variables:
            if not element: return False
        return True
    

    all() 函数只是通过一系列bools /数字,如果它看到0或 False 则返回 False .

    sqrt() 函数只是执行数字的 square root .

    例如:

    >>> from math import sqrt
    >>> sqrt(9)
    >>> 3
    >>> sqrt(100)
    >>> 10
    

    num % x 部分返回num / x的 remainder .

    最后, range(2, int(sqrt(num))) 意味着它将创建一个从2开始并在 int(sqrt(num)+1) 结束的 list

    有关范围的更多信息,请查看website

    num > 1 部分只是检查变量 num 是否大于1,因为1和0不被视为素数 .

    我希望这有帮助:)

  • 64

    在Python中:

    def is_prime(n):
        return not any(n % p == 0 for p in range(2, int(math.sqrt(n)) + 1))
    

    从数学形式主义到Python的更直接的转换将使用 all(n % p != 0... ) ,但这需要严格评估p的所有值 . 如果找到True值, not any 版本可以提前终止 .

  • 0

    Primes数字javascript的最佳算法

    function isPrime(num) {
          if (num <= 1) return false;
          else if (num <= 3) return true;
          else if (num % 2 == 0 || num % 3 == 0) return false;
          var i = 5;
          while (i * i <= num) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
            i += 6;
          }
          return true
        }
    
  • 0

    One can use sympy .

    import sympy
    
    sympy.ntheory.primetest.isprime(33393939393929292929292911111111)
    
    True
    

    来自sympy docs . 第一步是寻找微不足道的因素,如果找到这些因素可以快速返回 . 接下来,如果筛子足够大,则在筛子上使用二分法搜索 . 对于较小的数字,使用已知在其范围内没有反例的碱基进行一组确定性的Miller-Rabin测试 . 最后,如果数量大于2 ^ 64,则执行强大的BPSW测试 . 虽然这是一个可能的主要测试,我们认为存在反例,但没有已知的反例

  • 2

    与已经提到的AKS算法类似的想法

    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;
    }
    
  • 0

    查找某个范围内的数字是否为素数 .

    #!usr/bin/python3
    
    def prime_check(*args):
        for arg in args:
            if arg > 1:     # prime numbers are greater than 1
                for i in range(2,arg):   # check for factors
                    if(arg % i) == 0:
                        print(arg,"is not Prime")
                        print(i,"times",arg//i,"is",arg)
                        break
                else:
                    print(arg,"is Prime")
    
                # if input number is less than
                # or equal to 1, it is not prime
            else:
                print(arg,"is not Prime")
        return
    
    # Calling Now
    prime_check(*list(range(101)))  # This will check all the numbers in range 0 to 100 
    prime_check(#anynumber)         # Put any number while calling it will check.
    
  • 1
    myInp=int(input("Enter a number: "))
    if myInp==1:
        print("The number {} is neither a prime not composite no".format(myInp))
    elif myInp>1:
        for i in range(2,myInp//2+1):
            if myInp%i==0:
                print("The Number {} is not a prime no".format(myInp))
                print("Because",i,"times",myInp//i,"is",myInp)
                break
        else:
            print("The Number {} is a prime no".format(myInp))
    else:
        print("Alas the no {} is a not a prime no".format(myInp))
    
  • -1

    你可以尝试这样的事情 .

    def main():
        try:
            user_in = int(input("Enter a number to determine whether the number is prime or not: "))
        except ValueError:
            print()
            print("You must enter a number!")
            print()
            return
        list_range = list(range(2,user_in+1))
        divisor_list = []
        for number in list_range:
            if user_in%number==0:
                divisor_list.append(number)
        if len(divisor_list) < 2:
            print(user_in, "is a prime number!")
            return
        else:
            print(user_in, "is not a prime number!")
            return
    main()
    
  • 0

    以前的大多数答案都是正确的,但这里还有一种方法可以测试数字是素数 . 作为复习, prime numbers 是大于1的整数,其唯一因子是1和它本身 . (source

    Solution:

    通常情况下,您可以构建一个循环并开始测试您的号码,看它是否可以被1,2,3整除......直到您正在测试的数字......等但是为了减少检查时间,您可以将您的号码除以数字值的一半,因为数字不能被任何超过其值的一半的任何值整除 . 例如,如果要查看100是素数,则可以循环到50 .

    Actual code

    def find_prime(number):
        if(number ==1):
            return False
        # we are dividiing and rounding and then adding the remainder to increment !
        # to cover not fully divisible value to go up forexample 23 becomes 11
        stop=number//2+number%2
        #loop through up to the half of the values
        for item in range(2,stop):
            if number%item==0:
               return False
            print(number)
        return True
    
    
    if(find_prime(3)):
        print("it's a prime number !!")
    else:
        print("it's not a prime")
    
  • 0

    我们可以使用java流在O(sqrt(n))中实现它;考虑到noneMatch是一个shortCircuiting方法,当发现不需要确定结果时停止操作:

    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    System.out.println(n == 2 ? "Prime" : IntStream.rangeClosed(2, ((int)(Math.sqrt(n)) + 1)).noneMatch(a -> n % a == 0) ? "Prime" : "Not Prime");
    
  • 0

    在Java-8流和lambdas的帮助下,它可以在几行中实现:

    public static boolean isPrime(int candidate){
            int candidateRoot = (int) Math.sqrt( (double) candidate);
            return IntStream.range(2,candidateRoot)
                    .boxed().noneMatch(x -> candidate % x == 0);
        }
    

    性能应接近O(sqrt(N)) . 也许有人发现它很有用 .

  • 1

    我比较了最受欢迎的建议的效率,以确定一个数字是否为素数 . 我在 ubuntu 17.10 上使用了 python 3.6 ;我测试的数字高达100.000(您可以使用下面的代码测试更大的数字) .

    第一个图比较了函数(在我的答案中进一步解释),表明在增加数字时,最后一个函数的增长速度不如第一个函数快 .

    plot1

    在第二个图中,我们可以看到,在素数的情况下,时间稳定增长,但非素数不会在时间上如此快速地增长(因为大多数数字可以在早期被消除) .

    plot2

    以下是我使用的功能:

    def is_prime_1(n):
        return n > 1 and all(n % i for i in range(2, int(math.sqrt(n)) + 1))
    
    def is_prime_2(n):
        if n <= 1:
            return False
        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
    
    def is_prime_3(n):
        if n <= 1:
            return False
    
        if n % 2 == 0 and n > 2:
            return False
    
        for i in range(3, int(math.sqrt(n)) + 1, 2):
            if n % i == 0:
                return False
    
        return True
    
    • 我把其他答案中的一些想法混合成一个新的:
    def is_prime_4(n):
        if n <= 1:          # negative numbers, 0 or 1
            return False
        if n <= 3:          # 2 and 3
            return True
        if n % 2 == 0 or n % 3 == 0:
            return False
    
        for i in range(5, int(math.sqrt(n)) + 1, 2):
            if n % i == 0:
                return False
    
        return True
    

    这是我的脚本来比较变体:

    import math
    import pandas as pd
    import seaborn as sns
    import time
    from matplotlib import pyplot as plt
    
    
    def is_prime_1(n):
        ...
    def is_prime_2(n):
        ...
    def is_prime_3(n):
        ...
    def is_prime_4(n):
        ...
    
    default_func_list = (is_prime_1, is_prime_2, is_prime_3, is_prime_4)
    
    def assert_equal_results(func_list=default_func_list, n):
        for i in range(-2, n):
            r_list = [f(i) for f in func_list]
            if not all(r == r_list[0] for r in r_list):
                print(i, r_list)
                raise ValueError
        print('all functions return the same results for integers up to {}'.format(n))
    
    def compare_functions(func_list=default_func_list, n):
        result_list = []
        n_measurements = 3
    
        for f in func_list:
            for i in range(1, n + 1):
                ret_list = []
                t_sum = 0
                for _ in range(n_measurements):
                    t_start = time.perf_counter()
                    is_prime = f(i)
                    t_end = time.perf_counter()
    
                    ret_list.append(is_prime)
                    t_sum += (t_end - t_start)
    
                is_prime = ret_list[0]
                assert all(ret == is_prime for ret in ret_list)
                result_list.append((f.__name__, i, is_prime, t_sum / n_measurements))
    
        df = pd.DataFrame(
            data=result_list,
            columns=['f', 'number', 'is_prime', 't_seconds'])
        df['t_micro_seconds'] = df['t_seconds'].map(lambda x: round(x * 10**6, 2))
        print('df.shape:', df.shape)
    
        print()
        print('', '-' * 41)
        print('| {:11s} | {:11s} | {:11s} |'.format(
            'is_prime', 'count', 'percent'))
        df_sub1 = df[df['f'] == 'is_prime_1']
        print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
            'all', df_sub1.shape[0], 100))
        for (is_prime, count) in df_sub1['is_prime'].value_counts().iteritems():
            print('| {:11s} | {:11,d} | {:9.1f} % |'.format(
                str(is_prime), count, count * 100 / df_sub1.shape[0]))
        print('', '-' * 41)
    
        print()
        print('', '-' * 69)
        print('| {:11s} | {:11s} | {:11s} | {:11s} | {:11s} |'.format(
            'f', 'is_prime', 't min (us)', 't mean (us)', 't max (us)'))
        for f, df_sub1 in df.groupby(['f', ]):
            col = df_sub1['t_micro_seconds']
            print('|{0}|{0}|{0}|{0}|{0}|'.format('-' * 13))
            print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
                f, 'all', col.min(), col.mean(), col.max()))
            for is_prime, df_sub2 in df_sub1.groupby(['is_prime', ]):
                col = df_sub2['t_micro_seconds']
                print('| {:11s} | {:11s} | {:11.2f} | {:11.2f} | {:11.2f} |'.format(
                    f, str(is_prime), col.min(), col.mean(), col.max()))
        print('', '-' * 69)
    
        return df
    

    运行函数 compare_functions(n=10**5) (数字最多为100.000)我得到这个输出:

    df.shape: (400000, 5)
    
     -----------------------------------------
    | is_prime    | count       | percent     |
    | all         |     100,000 |     100.0 % |
    | False       |      90,408 |      90.4 % |
    | True        |       9,592 |       9.6 % |
     -----------------------------------------
    
     ---------------------------------------------------------------------
    | f           | is_prime    | t min (us)  | t mean (us) | t max (us)  |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_1  | all         |        0.57 |        2.50 |      154.35 |
    | is_prime_1  | False       |        0.57 |        1.52 |      154.35 |
    | is_prime_1  | True        |        0.89 |       11.66 |       55.54 |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_2  | all         |        0.24 |        1.14 |      304.82 |
    | is_prime_2  | False       |        0.24 |        0.56 |      304.82 |
    | is_prime_2  | True        |        0.25 |        6.67 |       48.49 |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_3  | all         |        0.20 |        0.95 |       50.99 |
    | is_prime_3  | False       |        0.20 |        0.60 |       40.62 |
    | is_prime_3  | True        |        0.58 |        4.22 |       50.99 |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_4  | all         |        0.20 |        0.89 |       20.09 |
    | is_prime_4  | False       |        0.21 |        0.53 |       14.63 |
    | is_prime_4  | True        |        0.20 |        4.27 |       20.09 |
     ---------------------------------------------------------------------
    

    然后,运行函数 compare_functions(n=10**6) (数字高达1.000.000)我得到这个输出:

    df.shape: (4000000, 5)
    
     -----------------------------------------
    | is_prime    | count       | percent     |
    | all         |   1,000,000 |     100.0 % |
    | False       |     921,502 |      92.2 % |
    | True        |      78,498 |       7.8 % |
     -----------------------------------------
    
     ---------------------------------------------------------------------
    | f           | is_prime    | t min (us)  | t mean (us) | t max (us)  |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_1  | all         |        0.51 |        5.39 |     1414.87 |
    | is_prime_1  | False       |        0.51 |        2.19 |      413.42 |
    | is_prime_1  | True        |        0.87 |       42.98 |     1414.87 |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_2  | all         |        0.24 |        2.65 |      612.69 |
    | is_prime_2  | False       |        0.24 |        0.89 |      322.81 |
    | is_prime_2  | True        |        0.24 |       23.27 |      612.69 |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_3  | all         |        0.20 |        1.93 |       67.40 |
    | is_prime_3  | False       |        0.20 |        0.82 |       61.39 |
    | is_prime_3  | True        |        0.59 |       14.97 |       67.40 |
    |-------------|-------------|-------------|-------------|-------------|
    | is_prime_4  | all         |        0.18 |        1.88 |      332.13 |
    | is_prime_4  | False       |        0.20 |        0.74 |      311.94 |
    | is_prime_4  | True        |        0.18 |       15.23 |      332.13 |
     ---------------------------------------------------------------------
    

    我使用以下脚本绘制结果:

    def plot_1(func_list=default_func_list, n):
        df_orig = compare_functions(func_list=func_list, n=n)
        df_filtered = df_orig[df_orig['t_micro_seconds'] <= 20]
        sns.lmplot(
            data=df_filtered, x='number', y='t_micro_seconds',
            col='f',
            # row='is_prime',
            markers='.',
            ci=None)
    
        plt.ticklabel_format(style='sci', axis='x', scilimits=(3, 3))
        plt.show()
    
  • 0

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

    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 的定义 .

  • -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;
    }
    
  • 1
    public static boolean isPrime(int number) {
     if(number < 2)
       return false;
     else if(number == 2 || number == 3)
            return true;
          else {
            for(int i=2;i<=number/2;i++)
               if(number%i == 0)
                 return false;
               else if(i==number/2)
                    return true;
          }
        return false;
    }
    

相关问题