zhb8015

posts(23) comments(6) trackbacks(0)
  • BlogJava
  • 联系
  • RSS 2.0 Feed 聚合
  • 管理

常用链接

  • 我的随笔
  • 我的评论
  • 我的参与
  • 最新评论

留言簿

  • 给我留言
  • 查看公开留言
  • 查看私人留言

随笔分类

  • hadoop

随笔档案

  • 2013年3月 (1)
  • 2012年10月 (2)
  • 2012年8月 (2)
  • 2012年7月 (1)
  • 2012年6月 (1)
  • 2012年5月 (1)
  • 2012年4月 (5)

文章分类

  • arithmetc
  • books(2)
  • design patter(4)
  • English(1)
  • exception(3)
  • hadoop(1)
  • interview(53)
  • Kent Beck
  • linux,unix(1)
  • MartinFlow(7)
  • method(7)
  • middleware(1)
  • projectManagement(6)
  • soa(9)
  • ssh(14)
  • ThoughtWork(2)
  • tibco(13)

文章档案

  • 2013年4月 (1)
  • 2013年3月 (3)
  • 2012年8月 (1)
  • 2012年7月 (8)
  • 2012年6月 (15)
  • 2012年5月 (14)
  • 2012年4月 (22)
  • 2012年3月 (5)

相册

  • java

搜索

  •  

最新评论

  • 1. re: Log4j详细配置（转）
  • 写得很详细，最后那句好像有点小问题，输出到test1和stdout应该是log4j.logger.myTest1=DEBUG, test1, stdout ?
  • --aramxiao
  • 2. re: 结合Maven2进行J2EE项目构建(转)
  • 评论内容较长,点击标题查看
  • --最代码
  • 3. re: java深浅复制
  • 评论内容较长,点击标题查看
  • --zhb8015
  • 4. re: 求质数，难以理解的代码，有兴趣可以看一下
  • 评论内容较长,点击标题查看
  • --zhb8015
  • 5. re: Advice about migrating to new platfrom
  • platfrom or platform??
  • --qingyue

阅读排行榜

评论排行榜

View Post

求质数，难以理解的代码，有兴趣可以看一下

求1.。x的质数？这样的问题相信大家都很熟悉，我这里有两个版本，其中有一点不太明白，希望大家指点一下。
一、简单的版本
二、复杂但艺术的版本(write by Robert C. Martin）
问题：都用到了Math.sqrt(x),为什么用平方根，原理是什么呢？

一、简单的版本
public static boolean isPrime(int x) {
        boolean result = true;
        int max = (int)Math.sqrt(x);
        
        if(x == 0 || x == 1) {
            result = false;
        }
        
        for(int i = 2; i <= max; i++) {
            if(x % i == 0) {
                result = false;
                break;
            }
        }
        return result;
    }

二、复杂但艺术的版本(write by Robert C. Martin）
 1public class PrimeGenerate1 {
 2    private static boolean[] crossOut;
 3    private static int[] result;
 4    
 5    /** *//**
 6     * @param maxValue  is the generation limit.
 7     * @return int[]
 8     */
 9    public static int[] generatePrime(int maxValue) {
10        if(maxValue < 2) {
11            return new int[0];
12        } else {
13            initializeArrayOfIntegers(maxValue);
14            crossOutMultiples();
15            putUncrossIntegerIntoResult();
16            iterateArray(result);
17            
18            return result;
19        }
20    }
21
22    /** *//**
23     * @param s
24     * @return
25     */
26    private static void initializeArrayOfIntegers(int maxValue) {
27        crossOut = new boolean[maxValue + 1];
28        for (int i = 2; i < crossOut.length; i++) 
29            crossOut[i] = false;
30    }
31    
32    private static void crossOutMultiples() {
33        int maxPrimeFactor = calMaxPrimeFactor();
34        for (int i = 2;i <= maxPrimeFactor; i++) {
35            if(notCrossed(i)) 
36                crossOutMultiplesOf(i);
37        }
38    }
39
40    /** *//**
41     * @param i
42     * @return
43     */
44    private static boolean notCrossed(int i) {
45        return crossOut[i] == false;
46    }
47
48    /** *//**
49     * @return
50     */
51    private static int calMaxPrimeFactor() {
52        double maxPrimeFactor = Math.sqrt(crossOut.length);
53        return (int)maxPrimeFactor;
54    }
55    
56    private static void putUncrossIntegerIntoResult() {
57        result = new int[numberOfUncrossedIntegers()];
58        for(int i = 2, j = 0; i < crossOut.length; i++) {
59            if(notCrossed(i))
60                result[j++] = i;
61        }
62    }
63
64    /** *//**
65     * @param count
66     * @return
67     */
68    private static int numberOfUncrossedIntegers() {
69        int count = 0;
70        for (int i = 2; i < crossOut.length; i++) {
71            if(notCrossed(i)) {
72                count++;    
73            }
74        }
75        return count;
76    }
77    
78    private static void iterateArray(int[] array) {
79        if(array.length != 0) {
80            for(int i : array) {
81                System.out.print(i + " ");
82            }
83            System.out.println();
84        }
85    }
86    
87    private static void crossOutMultiplesOf(int i) {
88        for (int multiple = 2 * i; multiple < crossOut.length; multiple += i) {
89            crossOut[multiple] = true;
90        }
91    }
92
93}


posted on 2012-04-12 16:21 zhb8015 阅读(434) 评论(1)  编辑  收藏 所属分类: interview

View Comments

# re: 求质数，难以理解的代码，有兴趣可以看一下  回复  更多评论   
Robert C. Martin's explation:


/**
* Every multiple in the array has a prime factor that
* is less than or equal to the root of the array size,
* so we don't have to cross of multiples of numbers
* larger than that root.
*/
2012-04-12 17:52 | zhb8015
新用户注册  刷新评论列表  

只有注册用户登录后才能发表评论。
网站导航:
博客园   IT新闻   Chat2DB   C++博客   博问   管理
相关文章:
  • Nutch vs Lucene(转)
  • ArrayList空间增长是怎么样的
  • 手工打包（jar）
  • TW interview experience(转)
  • 排序算法（转）
  • 加密算法（转）
  • 软件设计过程一些术语 AN BD FD DD CD CT
  • Log4j详细配置（转）
  • log4j详解
  • 时间复杂度
 
 
Powered by:
BlogJava
Copyright © zhb8015