[数据结构与算法]质数相关优化算法

目录

判断一个数是否是质数

求小于n的质数的个数

判断一个数是否是质数

优化版

public static boolean isPrim(int n){
    if(n<=3){
        return n>1;
    }
    if(n%6!=1 && n%6!=5){
        return false;
    }
    int k = (int)Math.sqrt(n);
    for(int i=5;i<=k;i++){
        if(n%i==0 || n%(i+2)==0){
            return false;
        }
    }
    return true;
}

求小于n的质数的个数

如果一个数x是质数，那么2x，3x，4x…，xx，……都不是质数，利用这一点，我们可以大大降低遍历的时间复杂度
用一个数组标记一个数是否是质数，是设为1，否设为0

?

public int countPrim(int n){
    int count = 0;
    int[] isPrim = new int[n];
    Arrays.fill(isPrim, 1);
    for(int i=2;i<n;i++){
        if(isPrim[i]==1){
            count++;
            if((long)i*i<n){
                for(int j=i;j*i<n;j++){
                    isPrim[j*i] = 0;
                }
            }
        }
    }
    count;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖