Java:输出1~20000内的所有素数,按每行5个打印出来

飞在秋天的蝴蝶
• 阅读 579

    public static void main(String[] args) {
        int x,y;
        int k=0;
        for(x=2;x<=1000;x++) {  //1~1000的素数从2开始
            boolean flag=true;
            for(y=2;y<x;y++) {
                if(x%y==0) {
                    flag=false;
                    break;
                }
            }//判断是否是素数
            if(flag) {
                k++;//如果是素数,k+1
                System.out.print(y+"\t");
                if(k%5==0) 
                    System.out.println(x);//每5个进行输出
            }
        }
        }
    }

分析:函数中最费时的部分是对素数的判断,因为这里有嵌套的双循环,增加了算法的时间复杂度,可以从三个方面改进: 1、 对素数的判断仿佛进行改进,从判断除以本身能否除尽,改进为除以本身数字的平方 2、 减少循环次数,因为偶数不可能是素数,所以x直接+2 3、 把判断是否是素数重新写一个方法里,然后在main方法中调用

改进后的代码:

  public class Su2 {
    public static void main(String[] args) {
        int k=0;//计数
        System.out.println("2 ");
        for (int i = 3; i <= 1000; i=i+2) {//外层被除数 ,因为偶数不可能是素数,所以直接+2

            if(isPrime(i))//在main方法中调用isPrime(int p)
            {
                k++;
                System.out.print(i);
            if(k%5==0) 
                    System.out.println("\n");//每5个进行转行

            }

        }
    }
    public static boolean isPrime(int p){//把判断是否是素数重新写一个方法里
        for (int j = 3; j <= Math.sqrt(p); j++) {//内层除数,利用Math.sqrt求i的平方根可以减少循环次数

            if(p % j == 0)
                return false;
        }
        return true;
    }
}
点赞
收藏
评论区
推荐文章
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
C语言函数:用位运算交换的方法交换两个变量值
void inplace_swap(int x, int y){    y  x ^ y; //Step 1    x  x ^ y; //Step 2    y  x ^ y; //Step 3 }int main(){  
Stella981 Stella981
3年前
Lua 学习记录
Lua可以对多个变量同时赋值,变量列表和值列表的各个元素用逗号分开赋值语句右边的值会依次赋给左边的变量a,b  1,2赋值语句会先计算右边所有的值然后再执行赋值操作x  1;y  2x, y  y, x变量个数\值的个数按变量个数补足nil变量个数<值的个数多余的值会被忽略a
Wesley13 Wesley13
3年前
oracle多表查询之经典面试题
一、笛卡尔积1.概念笛卡尔乘积是指在数学中,两个集合_X_和_Y_的笛卡尓积(Cartesianproduct),又称直积,表示为_X_×_Y_,第一个对象是_X_的成员而第二个对象是_Y_的所有可能有序对的其中一个成员。\1\简单点说就是:集合X的每个元素和集合B的每个元素进行两两组合,组合次数等于集合X元素数量
Stella981 Stella981
3年前
D3.js area函数
!(http://static.oschina.net/uploads/space/2015/0402/110259_Cfoo_861926.png)var area  d3.svg.area().interpolate("monotone").x(function(d) { return x(d.date); }).y0(260).y1(
Stella981 Stella981
3年前
Julia
算术运算符算术运算符适用于所有的基本数值类型x,一元加法,就是x本身\x,一元减法,x的相反数xy,二元加法,做加法运算xy,二元减法,做减法运算x\y,乘法,做乘法运算x/y,除法,做除法运算x^y,乘方,x的y次幂x%y,取余,x除以y然后取余数,等价于
Wesley13 Wesley13
3年前
MySQL中的数值函数
常用数值函数函  数功  能ABS(x)返回数值x的绝对值CEIL(x)返回大于或等于x的最小整数值FLOOR(x)返回小于或等于x的最大整数值MOD(x,y)返回x除以y的余数RAND()返回0~1内的随机数ROUND(x,y)返回x四舍五入后有y位小数的数值TRUNCATE(
Wesley13 Wesley13
3年前
常用模块之
importdatetimeimporttimeprint(time.strftime('%y/%m/%d%X'))输出结果:18/06/0520:40:46print(time.strftime('%Y/%m/%d%X'))输出结果:2018/06/
Wesley13 Wesley13
3年前
PHP字符串函数
<?php$x10;$x$x;echo$x;//输出10$c10;$c$c;echo$c;//输出10$y10;$y$y;echo$y;//输出10$z10;$z
Wesley13 Wesley13
3年前
MYSQL表分区支持的函数清单
Mysql5.1支持的partition函数1.数学函数ABS(x)    返回x的绝对值CEILING(x)/CEIL(x)返回大于或等于x的最小整数FLOOR(x)    返回小于或等于x的最大整数MOD(x,y)    返回x除以y以后的余数2.日期时间函数EXTRACT(typeFROMd)    从