嫩草研究院在线,最新亚洲伊人网,日本韩国欧美在线

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）

public class PrimeGenerate1 {
2

private static boolean[] crossOut;
3

private static int[] result;
4

/**
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

return result;
19

}
20

}
21

/**
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

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

/**
41

* @param i
42

* @return
43

*/
44

private static boolean notCrossed(int i) {
45

return crossOut[i] == false;
46

}
47

/**
49

* @return
50

*/
51

private static int calMaxPrimeFactor() {
52

double maxPrimeFactor = Math.sqrt(crossOut.length);
53

return (int)maxPrimeFactor;
54

}
55

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

/**
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

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

private static void crossOutMultiplesOf(int i) {
88

for (int multiple = 2 * i; multiple < crossOut.length; multiple += i) {
89

crossOut[multiple] = true;
90

}
91

}
92

}

posted on 2012-04-12 16:21 zhb8015 閱讀(433) 評論(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詳解時間復雜度

zhb8015

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

相冊

搜索

最新評論

閱讀排行榜

評論排行榜

View Post

求質數，難以理解的代碼，有興趣可以看一下

View Comments

# re: 求質數，難以理解的代碼，有興趣可以看一下 回復 更多評論

zhb8015

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

相冊

搜索

最新評論

閱讀排行榜

評論排行榜

View Post

求質數，難以理解的代碼，有興趣可以看一下

View Comments

# re: 求質數，難以理解的代碼，有興趣可以看一下 回復 更多評論

# re: 求質數，難以理解的代碼，有興趣可以看一下回復更多評論