关于素数:面试官你知道怎么求素数吗

摘要：面试官：你晓得怎么求素数吗？我：求素数？

本文分享自华为云社区《很多人不晓得的求素数的正确办法》，原文作者：bigsai。

当初的面试官，是有数开发者的梦魇，可能吊打面试官的属实不多，因为大部分面试官真的有那么那几下子。但在面试中，咱们这些小生存者不能全盘否定只能单点冲破—从某个问题上让面试官眼前一亮。这不，明天就来分享来了。

这年头，算法岗内卷不说，开发岗也有点内卷，对开发者要求越来越高了，而面试官也是挖空心思的“刁难”面试者，但凡都喜爱由浅入深，但凡都喜爱问个：你晓得为什么？你晓得原理吗？之类。并且，以前只是大厂面试官喜爱问算法，大厂员工底子好，很多甚至有 ACM 教训或者零碎刷题教训，这很容易了解，但当初一些小公司面试官也是张口闭口 xx 算法、xx 数据结构你说说看，这不，真的被问到了。

在这么一次的过程，面试官问我算法题我不吃惊，我实现早把十大排序原理、复杂度剖析、代码手写实现进去了，也把链表、树的各种操作复习的滚瓜烂熟，不过忽然就是很惊讶的面试官来了一道求素数问题，我把场景还原一下：

面试官：你晓得怎么求素数吗？

我：求素数？

面试官：是的，就是求素数。

我：这很简略啊，判断一个数为素数，那么必定就没有两个数 (除了本身和 1) 相乘等于它，只须要枚举看看有没有可能被它整除的数就能够了，如果有那么就不是素数，如果没有，那么就是素数。

面试官露出一种悲观的表情，说我说的对，但没答到点子上，让我具体说一下。

上面开始开始我的表演：

首先，最笨的办法 ，判断 n 是否为素数，就是枚举[2,n-1] 之间有没有间接可能被 n 整除的，如果有，那么返回 false 这个就不是素数，否则就是素数，代码如下：

boolean isprime(int value){for(int i=2;i<value;i++)
  {if(value%i==0)
       {return false;}
  }
    return true;
}

这种判断一个素数的工夫复杂度为 O(n).

然而其实这种太浪费时间了，齐全没必要这样，能够优化一下。如果一个数不是质数，那么必然是两个数的乘积，而这两个数通常一个大一个小，并且小的小于等于根号 n，大的大于等于根号 n，咱们只须要枚举小的可能范畴，看看是否可能被整除，就能够判断这个数是否为素数啦。例如 100=250=425=520=1010 只须要找 2—10 这个区间即可。右侧的肯定有个对应的不须要管它。

boolean isprime(int value)
{for(int i=2;i*i<value+1;i++)
    {if(value%i==0)
       {return false;}
    }
    return true;
}

这里之所以要小于 value+1，就是要蕴含根号的状况，例如 3*3=9. 要蕴含 3. 这种工夫复杂度求单个数是 O(sqrt(n))。面试官我给你画张图让你看看其中区别：

说到这里面试官露出快慰的笑容。

面试官：不错不错，基本点把握了

我：老哥，其实求素数精华不在这，这个太低效在很多时候，比方求小于 n 的所有素数，你看看怎么搞？

面试官：用个数组用第二种办法求 O(n*sqrt(n))还行啊。

求多个素数的时候(小于 n 的素数)，下面的办法就很繁琐了，因为有大量反复计算，因为计算某个数的倍数是否为素数的时候呈现大量的反复计算，如果这个数比拟大那么对空间节约比拟多。

这样，素数筛的概念就被创造和应用。筛的原理是从返回后进行一种递推、过滤排序以来统计素数。

咱们看一个数如果不是为素数，那么这个数没有数的乘积能为它，那么这样咱们能够依据这个思维进行操作啊：

间接从前往后枚举，这个数地位没被标记的必定就是素数，如果这个数是素数那么将这个数的倍数标记一下 (下次遍历到就不须要在计算)。如果不是素数那么就进行下一步。这样数值越大前面计算次数越少，在进行具体操作时候可借助数组进行判断。 所以埃氏筛的核心思想就是将素数的倍数确定为合数。

假如刚开始全是素数，2 为素数，那么 2 的倍数均不是素数；而后遍历到 3，3 的倍数标记一下；下个是 5(因为 4 曾经被标记过)；始终到 n - 1 为止。具体流程能够看图：

具体代码为：

boolean isprime[];
long prime[];
void getprime()
{prime=new long[100001];// 记录第几个 prime
      int index=0;// 标记 prime 以后下标
        isprime=new boolean [1000001];// 判断是否被标记过
        for(int i=2;i<1000001;i++)
        {if(!isprime[i])
            {prime[index++]=i;
            }
            for(int j=i+i;j<1000000;j=j+i)// 他的所有倍数都 over
            {isprime[j]=true;                    
            }
        }
}

这种筛的算法复杂度为 O(nloglogn); 别小瞧多的这个 logn，数据量大一个 log 可能少不少个 0，那工夫也是十倍百倍甚至更多的差距。

面试官曾经开始拍板同意了，哦哦的叫了起来，可其实还没完。还有个线性筛—欧拉筛。察看上述的埃氏筛，有很多反复的计算，尤其是后面的素数，比方 2 和 3 的最小公倍数为 6，每 3 次 2 的计算就也会遇到是 3 的倍数，而欧拉筛在埃氏筛的根底上改良，无效的防止了这个反复计算。

具体是何种思路呢？就是埃氏筛是遇到一个质数将它的倍数计算到底，而欧拉筛则是只用 它乘以已通晓的素数的乘积进行标记，如果素数可能被整除那就进行往后标记。

在实现上同样也是用两个数组，一个存储真实有效的素数，一个用来作为标记应用。

在遍历到一个数的时候，如果这个数没被标记，那么这个数存在素数的数组中，对应下标加 1.
不论这个数是不是素数，遍历已知素数将它和该素数的乘积值标记，如果这个素数可能被以后值 i 整除，那么进行操作进行下一轮。

具体实现的代码为：

boolean isprime[];
int prime[];
void getprimeoula()// 欧拉筛
{prime = new int[100001];// 记录第几个 prime
        int index = 0;
        isprime = new boolean[1000001];
        for (int i = 2; i < 1000001; i++) {if (!isprime[i]) {prime[index++] = i;
            }
            for (int j = 0; j < index && i * prime[j] <= 100000; j++){// 已知素数范畴内枚举
                isprime[i * prime[j]] = true;// 标记乘积
                if (i % prime[j] == 0)
                    break;
            }
        }
}

你可能会问为啥 if (i % prime[j] == 0)就要 break。

如果 i%prime[j]==0，那么就阐明 i =prime[j]*k. k 为一个整数。
那么如果进行下一轮的话
iprime[j+1]=(prime[j]k)prime[j+1]=prime[j](kprime[j+1]) 当 i =kprime[j+1] 两个地位就产生抵触反复计算啦, 所以一旦遇到可能被整除的就进行。

你能够看到这个过程，6 只标记 12 而不标记 18，18 被 9 * 2 标记。具体了解还须要多看看代码想想。过程图就不画啦！欧拉的思路就是离我较近的我给它标记。欧拉筛的工夫复杂度为 O(n)，因为每个数只标记一次。

面试官露出一脸观赏的表情，说了句不错，上面就是聊聊家常，让我期待下一次面试！

点击关注，第一工夫理解华为云陈腐技术~

关于素数:面试官你知道怎么求素数吗

前言

求一个质数

求多个素数

埃拉托斯特尼 (Eratosthenes) 筛法

欧拉筛