算法求100以内的质数

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法求100以内的质数，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1371字，纯文字阅读大概需要2分钟。

内容图文

质数概念：
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。例如：7只能被1和7整除，除此之外不能再被其他数字整除，7就是质数。6能被2,3整除，6就不是质数。
最小的质数是2，它也是唯一的偶数质数。最前面的质数依次排列为：2，3，5，7，11，13，17，19，23，29，31等。

分析过程：
1、从2开始遍历，如果这个数能被从2到小于它本身前一个数整除，那么这个数就不是质数
2、如果判断能够被整除，此时打个标记，标记这个数不是质数。
3、将所有被标记为质数的数，打印出来。

代码片段：

public class PrimeNumber {
    public static void main(String[] args) {
        int i, j;
        //定义一个标志位，默认所有数都是质数
        boolean IsPrime=true;

        for (i = 2; i <= 100; i++) {
            IsPrime=true;
            for (j = 2; j < i; j++) {
                if ( i%j ==0) {
                    //如果能被整除，那么这个数就不是质数，这里标记下不是质数
                    IsPrime=false;
                    break;
                }
            }
            //break会跳出最近的一个循环体，即跳到这里
            if(IsPrime) {
                System.out.print(i + "\t");
            }
        }
    }
}

输出结果：

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	

算法优化：
第 1 次优化：
将判断能否被整除的循环过程减半，如果从2到(i-1)中能被整除，那么从2到(i/2)也能被整除。所以只需判断从2到(i/2)能否被整除即可，注意这里包含等于(i/2)的数。
即把原来的

for (j = 2; j < i; j++) 

替换为

for (j = 2; j < =i/2; j++) 

第 2 次优化：
如果从2到(i/2)能被整除，那么可以直接判断从2到 i 开平方中间能否被整除即可。这里用到一个方法Math.sqrt(i)，表示 i 开平方。
即替换为

for (j = 2; j <= Math.sqrt(i); j++)

内容总结

以上是互联网集市为您收集整理的算法求100以内的质数全部内容，希望文章能够帮你解决算法求100以内的质数所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---