判断素数,素数筛

时间:2022-02-23作者:klpeng分类:IT综合浏览:373评论:0

一、判断一个数是否为素数

  判断一个数是否是素数用到的是如下判别法:
如果大于1的整数a不能被所有不超过 a \sqrt{a} a 的素数整除,那么a一定是素数
 代码:

//判断a是否为素数,是返回true,不是返回false
boolean isPrime(int a){
        if(a<=1){
            return false;
        }
        for(int i =2 ; i <= Math.sqrt(a) ;i++){
            if( a%i == 0 ){
                return false;
            }
        }
        return true;
}

二、埃拉托斯特尼筛素数

 原理: 获取n以内的全部素数,必须把不大于 n \sqrt{n} n 的所有素数的倍数删除,剩下的就是素数
 代码:

	static int N = 1000010;
    static int primes [] = new int[N]; //存n以内的素数
    static int cnt; 
    static boolean st [] = new boolean[N]; //判断是否为素数
    static void get_primes(int n ){
        
        for(int i =2;i<=n;i++){
            if( st[i] ){
                continue;
            }
            primes[cnt++] = i;
            for(int j = i+i;j<=n;j+=i){
                st[j] = true;
            }
        }
    
        
    }
打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢