与面试官的对话:100万以内的质数用Java怎么实现?

createh515小时前技术教程1

一个头发稀少、穿着格子衬衣的中年男子走了进来,把手里拿的MAC放在桌子上。

面试官说对我说:“我会用电脑记录面试过程,你不要介意啊”。

我回答道:“没关系。”

面试官:“先来一点基础的算法题吧,用Java写一个方法,求100万内的质数。

我心中暗想确实很基础,质数不就是除了1和自身外无法被其他数整除的数吗,于是便写下:

public static List findPrime(){
    List 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 findPrime(){
    List 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 findPrime(){
    List list = new ArrayList<>(100000);
    for (int n = 2; n < 1000000 n boolean isprime='true;' int sqrt='(int)' math.sqrtn for integer i : list if n i='= 0)' isprime='false;' break if i> sqrt) {
                break;
            }
        }
        if (isPrime) {
            list.add(n);
        }
    }
    return list;
}

我茅塞顿开,性能果然至少可以提升一倍,这次面试真的是学到了。

本故事纯属虚构,如有雷同实属巧合。

相关文章

Java编程入门100例之十

本文介绍用Java代码打印出100以内的素数:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97代码如下:pu...

这里的每一题都能提升你的java水平,10道java经典算法题!第二弹

10道java经典算法!注意文章末尾!【程序1】 题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? 1.程序分析:可填在百位、十位、个位的数字都是1、2、3、4。组成...

javaWeb RSA加密使用

加密算法在各个网站运用很平常,今天整理代码的时候看到了我们项目中运用了RSA加密,就了解了一下。先简单说一下RSA加密算法原理,RSA算法基于一个十分简单的数论事实:将两个大质数相乘十分容易,但是想要...

java面试必备:七个常见的Java算法问题和示例答案

#头条创作挑战赛#当面试Java算法问题时,根据不同的难度级别和特定的面试流程,以下是一些常见的Java算法问题和示例答案。问题1:如何判断一个字符串是回文字符串?示例答案:问题2:如何找到一个数组中...

初学者的玩具——Java经典小程序,问题源码详解

准备了一些java初级的小程序,关于java的知识点都被程序概括,选取最经典的一些介绍给大家。1、编写程序,判断给定的某个年份是否是闰年。 闰年的判断规则如下: (1)若某个年份能被4整除但不能被10...