3
面试真题：求100万内的质数
source link: https://blog.51cto.com/u_6740480/5146357
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
面试真题：求100万内的质数
原创一个头发稀少、穿着格子衬衣的中年男子走了进来，把手里拿的MAC放在桌子上，对我说：“我会用电脑记录面试过程，你不要介意啊”。
我回答到：“没关系。”
面试官：“先来一点基础的算法题吧，用Java写一个方法，求100万内的质数。”
我心中暗想确实很基础，质数不就是除了1和自身外无法被其他数整除的数嘛，于是便写下：
public static List<Integer> findPrime(){
List<Integer> list = new ArrayList<>(100000);
for (int n = 2; n < 1000000; n++) {
boolean isPrime = true;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
list.add(n);
}
}
return list;
}
面试官皱了一下眉头，说：“计算整除的时候，需要从2一直计算到n-1嘛？”
经过这么一提醒，我突然想起来整除计算到平方根就可以了，于是马上修改了代码：
public static List<Integer> findPrime(){
List<Integer> list = new ArrayList<>(100000);
for (int n = 2; n < 1000000; n++) {
boolean isPrime = true;
int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
list.add(n);
}
}
return list;
}
面试官看了看，说：“写的很好，功能基本上都实现了。不过再想想，有什么可以优化的地方？”
我想了想，说：“好像没有什么可以优化的？”
我左思右想一番，说：“应该没有吧。”
面试官说：“确定没有了嘛？”
我肯定地回答：“确定没有了。”
面试官：“好吧，这个问题先到这。”
我有点不服气，抢着问到：“您说说，还有什么可以优化的地方？”
面试官微笑了一下，说：“还可以利用之前计算出质数做整除就可以了，性能至少可以提升一倍。”
面试官在我写的代码上改了几笔，就变成了：
public static List<Integer> findPrime(){
List<Integer> list = new ArrayList<>(100000);
for (int n = 2; n < 1000000; n++) {
boolean isPrime = true;
int sqrt = (int) Math.sqrt(n);
for (Integer i : list) {
if (n % i == 0) {
isPrime = false;
break;
}
if (i > sqrt) {
break;
}
}
if (isPrime) {
list.add(n);
}
}
return list;
}
我茅塞顿开，这次面试真的是学到了。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK