zhb8015
posts(23)
comments(6)
trackbacks(0)
BlogJava
聯(lián)系
聚合
管理
常用鏈接
我的隨筆
我的評(píng)論
我的參與
最新評(píng)論
留言簿
給我留言
查看公開(kāi)留言
查看私人留言
隨筆分類(lèi)
hadoop
隨筆檔案
2013年3月 (1)
2012年10月 (2)
2012年8月 (2)
2012年7月 (1)
2012年6月 (1)
2012年5月 (1)
2012年4月 (5)
文章分類(lèi)
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)
相冊(cè)
java
搜索
最新評(píng)論
1.?re: Log4j詳細(xì)配置(轉(zhuǎn))
寫(xiě)得很詳細(xì),最后那句好像有點(diǎn)小問(wèn)題,輸出到test1和stdout應(yīng)該是log4j.logger.myTest1=DEBUG, test1, stdout ?
--aramxiao
2.?re: 結(jié)合Maven2進(jìn)行J2EE項(xiàng)目構(gòu)建(轉(zhuǎn))
評(píng)論內(nèi)容較長(zhǎng),點(diǎn)擊標(biāo)題查看
--最代碼
3.?re: java深淺復(fù)制
評(píng)論內(nèi)容較長(zhǎng),點(diǎn)擊標(biāo)題查看
--zhb8015
4.?re: 求質(zhì)數(shù),難以理解的代碼,有興趣可以看一下
評(píng)論內(nèi)容較長(zhǎng),點(diǎn)擊標(biāo)題查看
--zhb8015
5.?re: Advice about migrating to new platfrom
platfrom or platform??
--qingyue
閱讀排行榜
評(píng)論排行榜
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)
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
閱讀(439)
評(píng)論(1)
編輯
收藏
所屬分類(lèi):
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ù)雜度
Powered by:
BlogJava
Copyright © zhb8015
主站蜘蛛池模板:
定南县
|
翼城县
|
苏尼特右旗
|
双江
|
荔波县
|
运城市
|
河源市
|
渭南市
|
巩留县
|
新源县
|
阜城县
|
定州市
|
出国
|
个旧市
|
青神县
|
韶山市
|
潜山县
|
东乌珠穆沁旗
|
磐安县
|
七台河市
|
溧阳市
|
耿马
|
济源市
|
古交市
|
庆阳市
|
扬中市
|
伊吾县
|
颍上县
|
新竹市
|
仙游县
|
喀什市
|
玉环县
|
万盛区
|
彰化县
|
海阳市
|
社旗县
|
资源县
|
美姑县
|
宜宾县
|
红原县
|
晋宁县
|