一. 前言
本文介绍多种方式来实现“找出100以内的所有素数(质数)?100000以内的呢?”的需求。各种方式之间存在巨大差异,请认真体会代码含义,理解编程思想对于计算机程序运行的优劣。从而理解算法对于程序的重要性。
二、需求分析
素数(质数):只能被1和它本身整除的自然数。(注意:1不是素数)
例如:2、3、5、7、11、13、17、19、23、...
三.算法实现
实现方式1:
class PrimeNumberTest { long start = System.currentTimeMillis(); //记录当前时间距离1970-1-1 00:00:00的毫秒数
//判断i是否是质数 //重置isFlag,思考为什么要将isFlag重置? long end = System.currentTimeMillis(); } |
实现方式2:针对实现方式1进行优化
class PrimeNumberTest1 { int count = 0;//记录质数的个数 for(int i = 2;i <= 100000;i++){ //i boolean isFlag = true; //用于标识i是否被除尽过 //判断i是否是质数 long end = System.currentTimeMillis(); } |
解释:
优化1:表示如果查到计算到当前值并非质数,就不再进行下面的计算。比如:对15进行计算的时候,内层循环计算15%3==0,从而将flag设置为flase,那么如果没有break就会继续计算15%4。
优化2:思考这样一个问题“假设现在要找出100以内的质数,按照方式一的逻辑是怎样的?”。首先我们会从2开始直到100,也就是[2,100]。那么看接下来的式子:2*50=100,3*33.3 = 100,4*25=100,5*20=100,6*16.66=100。你发现了吗,如果对于当前判断数100来讲,随着被除数逐渐增大,除数逐渐减小。那么如果使用数字2判断出来100不是质数,那么使用50也能判断出100不是质数。这么说你或许就明白了。那么我们只需要判断到那个数值才算可以呢?那就是被除数和除数相等,即“被除数*除数=当前判断值,被除数=除数”,即“当前判断值开平方”。
实现方式3:使用continue + 标签
class PrimeNumberTest2 { int count = 0;//记录质数的个数 label:for(int i = 2;i <= 100000;i++){ //i long end = System.currentTimeMillis(); } |
思考一下这种方式优化在哪了?这么优化的好处是什么?
标签:以内,质数,System,isFlag,100000,println,100,out From: https://blog.csdn.net/weixin_44554794/article/details/140246381