|
何谓素数? 数学家们说 所谓素数就是因数除了1就是他们本身的自然数。 它们就是数学世界的颜值担当 自从欧（几里德）先生证明说 它的伙伴有无穷多后 无数数学家开始为之倾倒 有许多默默无闻的数学家 一直在不断地研究着这些高颜值数字 感兴趣的同学 可以翻看以下内容： http://www./cms/sxxw/20130529.htm IT、数学不分家 数学家感兴趣的内容 ITer也不能轻易放过 最近就有一个同学 迷上了她 “如何将100到200之间的素数很快地计算并输出？” 同学用JAVA实现如下 public static void main(String[] args) { for(int i=100; i<201;> boolean b=true; for(int j=2; j if(i%j==0){ b=false; } } if(b==true){ System.out.println(i); } } } 运行结果整齐如下 从结果来看 如果没数错的话 100-200之间 共有21个素数 同学说 这个问题的解决方案不太满意 这些代码要继续优化 但是遗憾的是 不知道从哪里开始 从算法的角度来看 是否最优 有两个维度 一是时间复杂度 另外一个就是空间复杂度 那么就从这里开始吧~ 于是 带着最初的梦想 迈着蹒跚的步伐 开始改进 第1版： 从时间的角度来看 节省若干次循环开销 public static void main(String[] args) { for(int i=100; i<201;> boolean b=true; for(int j=2; j; j++){ if(i%j==0){ b=false; } } if(b==true){ System.out.println(i); } } } 假设执行一次循环需要1个时间单位 那么这个改进会节省多少时间呢? 这个复杂的数学问题 就留给数学系的天才们吧 ITer们只销晓得 迈出这样一小步 节约开销一大步 就好~ 这样看来 节约时间还可以有其他版本啦~ 比如说 不要再执行到i/2 截止到i的平方根就好 可以不 有无数数学家说这样做是没问题的~ 程序也证明了这一点 于是就出现了 第2版： public static void main(String[] args) { for(int i=100; i<201;> boolean b=true; for(int j=2; j<>; j++){ if(i%j==0){ b=false; } } if(b==true){ System.out.println(i); } } } 各位要特别注意 在循环条件处要加上“=” 否则的话 121和169之类的数字就要粉墨登场了~ 可还有别的思路 能不能再节约点其他开销？ 试着思考以下问题：
当把这些问题想清楚后 又一个方案浮出水面 第3版： public static void main(String[] args) { int j; for(int i=100; i<201;> for(j=2; j<>; j++){ if(i%j==0){ break; } } if(j>(Math.sqrt(i))){ System.out.println(i); } } } Did you get it? If so 恭喜你 If no 回复我 如果您也诲人不烦 耐心看到了这里 那就再接受一个不情之请 动动小手指 把小文转发到你的圈中 不一定在哪里 就会有位需要的人 帮人一忙 胜造N级浮屠 |
|
|
来自： 梦回唐朝0ony8a > 《2017》
