zhb8015
posts(23)
comments(6)
trackbacks(0)
BlogJava
联系
聚合
管理
常用链接
我的随笔
我的评论
我的参与
最新评论
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
hadoop
随笔档案
2013年3月 (1)
2012年10月 (2)
2012年8月 (2)
2012年7月 (1)
2012年6月 (1)
2012年5月 (1)
2012年4月 (5)
文章分类
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)
相册
java
搜索
最新评论
1. re: Log4j详细配置(转)
写得很详细,最后那句好像有点小问题,输出到test1和stdout应该是log4j.logger.myTest1=DEBUG, test1, stdout ?
--aramxiao
2. re: 结合Maven2进行J2EE项目构建(转)
评论内容较长,点击标题查看
--最代码
3. re: java深浅复制
评论内容较长,点击标题查看
--zhb8015
4. re: 求质数,难以理解的代码,有兴趣可以看一下
评论内容较长,点击标题查看
--zhb8015
5. re: Advice about migrating to new platfrom
platfrom or platform??
--qingyue
阅读排行榜
评论排行榜
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
阅读(424)
评论(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新闻
知识库
C++博客
博问
管理
相关文章:
Nutch vs Lucene(转)
ArrayList空间增长是怎么样的
手工打包(jar)
TW interview experience(转)
排序算法(转)
加密算法(转)
软件设计过程一些术语 AN BD FD DD CD CT
Log4j详细配置(转)
log4j详解
时间复杂度