侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 39 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

经典算法4质数筛 算法质数的判断 使用质数筛VS不使用质数筛性能比较

SeaDream乄造梦
2022-04-05 / 0 评论 / 0 点赞 / 480 阅读 / 1,202 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

一、什么是质数

质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

二、质数编程语言的判断

  1. 对于很多数字a是否是质数的判断,我们需要每次都进行这样的操作:每个a都分别除以[2,a)中所有的数字,若不能被整除则认为这个数是质数。如果有很多这样子的a,我们知道每判断一个a要从新遍历a-2次,这样是非常浪费性能的。
  2. 我们是否可以把从0到所求最大数字max的所有质数全部提前标注存起来呢?答案是可以的。
  3. 实现思路:我们提前判断质数并都存到数组中(与0-max的数组下标与质数一一对应,是质数arr[x]==true,不是质数arr[x]==false),然后用数组下标直接取出true或false即可。这样的话,我们只需要遍历一次就解决了所有a的问题。
  4. 下面我们用三种方法来判断质数,这三种方法性能逐渐优化

三、不使用质数筛

方法一:不做任何处理
    public static boolean judge(int i) {
        if (i<2) {
            return false;
        }

        for (int j=2;j<i;j++) {
            if (i%j==0) {
                return false;
            }
        }
        return true;
    }
方法二:对方法一进行优化
	private static boolean isPrime(int src) {
        double sqrt = Math.sqrt(src);
        if (src < 2) {
            return false;
        }
        if (src == 2 || src == 3) {
            return true;
        }
        if (src % 2 == 0) {// 先判断是否为偶数,若偶数就直接结束程序
            return false;
        }
        for (int i = 3; i <= sqrt; i+=2) {
            if (src % i == 0) {
                return false;
            }
        }
        return true;
    }

四、使用质数筛初始化保存

1.将质数存到数组中,便于后面使用时不用从新遍历,直接取用数组下标
   public static boolean isp[] = new boolean[a];
   public static void Init() {
        //初始化,默认都是质数
        for (int i=2;i< isp.length;i++) {
            isp[i]=true;
        }
        // 不是质数的变为false
        for (int i=2;i< isp.length;i++){
            if (isp[i]) {
                /**  不断更新	isp 数组
                 * 第一轮数组下标为2的倍数变为 false,
                 * 第二轮数组下标为3的倍数变为 false
                 * 第三轮数组下标为4的倍数变为 false
                 * ...
                 * 从2-a所有的质数全部初始化成功
                 */
                for(int j=i*2;j< isp.length;j+=i) {  //j从++变为+i,而i的值从2开始不断累加
                    //System.out.println(i+" "+j);
                    isp[j] = false;
                }
            }
        }
    }       

2.数组初始化成功,见下图

在这里插入图片描述
判断哪个数字是不是质数,直接取用isp数组下标即可。

0

评论区