国产精品videossex久久发布 ,国产一区二区成人,精品在线免费视频

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）

1

public 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 閱讀(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詳解時間復雜度

主站蜘蛛池模板：丽江市| 上虞市| 大余县| 凌源市| 古丈县| 勃利县| 且末县| 西昌市| 襄城县| 崇义县| 翁源县| 梁山县| 清水县| 尉犁县| 宣威市| 阿合奇县| 永嘉县| 瑞安市| 吴江市| 乌拉特前旗| 汝州市| 东兰县| 集安市| 泸西县| 新余市| 景谷| 尖扎县| 大田县| 江北区| 通化市| 兴海县| 梨树县| 湖北省| 高州市| 安顺市| 比如县| 洛隆县| 两当县| 巍山| 隆德县| 武功县|