亚洲av永久无码天堂网,亚洲精品美女视频,亚洲暴爽 AV人人爽日日碰

View Post

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

求1.。x的質(zhì)數(shù)？這樣的問(wèn)題相信大家都很熟悉，我這里有兩個(gè)版本，其中有一點(diǎn)不太明白，希望大家指點(diǎn)一下。
一、簡(jiǎn)單的版本
二、復(fù)雜但藝術(shù)的版本(write by Robert C. Martin）
問(wèn)題：都用到了Math.sqrt(x),為什么用平方根，原理是什么呢？

一、簡(jiǎn)單的版本

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 閱讀(428) 評(píng)論(1) 編輯收藏所屬分類: interview

View Comments

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

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

新用戶注冊(cè) 刷新評(píng)論列表


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




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

zhb8015

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

相冊(cè)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

View Post

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

View Comments

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

zhb8015

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

相冊(cè)

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

View Post

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

View Comments

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

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