亚洲欧洲专线一区,亚洲婷婷在线视频,亚洲日本一区二区三区

View Post

求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下

求1.。x的質(zhì)數(shù)？這樣的問題相信大家都很熟悉，我這里有兩個版本，其中有一點不太明白，希望大家指點一下。
一、簡單的版本
二、復(fù)雜但藝術(shù)的版本(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;

}

二、復(fù)雜但藝術(shù)的版本(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 閱讀(427) 評論(1) 編輯收藏所屬分類: interview

View Comments

# re: 求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下 回復(fù) 更多評論

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

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: Nutch vs Lucene(轉(zhuǎn)) ArrayList空間增長是怎么樣的手工打包（jar） TW interview experience(轉(zhuǎn)) 排序算法（轉(zhuǎn)）加密算法（轉(zhuǎn)）軟件設(shè)計過程一些術(shù)語 AN BD FD DD CD CT Log4j詳細(xì)配置（轉(zhuǎn)） log4j詳解時間復(fù)雜度

zhb8015

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

相冊

搜索

最新評論

閱讀排行榜

評論排行榜

View Post

求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下

View Comments

# re: 求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下 回復(fù) 更多評論

zhb8015

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

相冊

搜索

最新評論

閱讀排行榜

評論排行榜

View Post

求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下

View Comments

# re: 求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下 回復(fù) 更多評論

# re: 求質(zhì)數(shù)，難以理解的代碼，有興趣可以看一下回復(fù) 更多評論