import java.util.*;
//重构前:根据所给出的数字n,返回1-n之间的所有质数.
class GeneratorPrimes
{
public static void main(String[] args)
{
long start = System.currentTimeMillis();
int[] a = PrimeGenerator.generate(10000000);
long end = System.currentTimeMillis();
//System.out.println(Arrays.toString(a));
System.out.println(end - start);
}
public static int[] generate(int maxValue) {
if (maxValue >= 2)
{
int s = maxValue + 1;
boolean[] f = new boolean[s];
int i;
for (i =0; i < s; i++)
{
f[i] = true;
}
f[0] = false;
f[1] = false;
int j;
for (i = 2; i < Math.sqrt(s) + 1; i++)
{
//此处对标识为true的元素不再进行标记.
if (f[i])
{
for (j = 2 * i; j < s; j += i)
{
f[j] = false;
}
}
}
int count = 0;
for (i = 0; i < s; i++)
{
if (f[i])
{
count++;
}
}
int[] primes = new int[count];
for (i = 0, j = 0; i < s; i++)
{
if (f[i])
{
primes[j++] = i;
}
}
return primes;
} else {
return new int[0];
}
}
}
/*
*重构后:根据所给出的数字n,返回1-n之间的所有质数.
*
*步骤:通过一个长度为这个数的boolean数组标识出这个数字之间的所有数字.
* 1-n之间的数字进行过滤,凡是能够分解质因数n*(2..n)都标记为true,表示已被过滤掉.
* 重复执行此步骤,至到上限值.
*/
class PrimeGenerator
{
private static boolean[] isCrossed;
private static int[] result;
public static int[] generate(int maxValue) {
if (maxValue < 2)
{
return new int[0];
} else {
initializeSieve(maxValue);
sieve();
loadPrimes();
return result;
}
}
private static void sieve() {
int limit = determineIterationLimit();
for (int i = 2; i <= limit; i++)
{
//如果已标识为过滤掉的数字则不再进行标记.
//因为对于n*(2..n),如果有n=x*y,则n*(2..n)=x*y*(2..n),已被完整标记过,n序列是x序列的一个子集.
if (notCrossed(i))
{
crossOutMultiplesOf(i);
}
}
}
//过滤掉的所有数字,标记为true.
private static void crossOutMultiplesOf(int i) {
for (int multiple = 2 * i; multiple < isCrossed.length; multiple += i)
{
isCrossed[multiple] = true;
}
}
//判断当前位置(i)数字是否被过滤掉.
//已过滤掉返回true
//未过滤掉返回false
private static boolean notCrossed(int i) {
return isCrossed[i] == false;
}
//上限值.上限值是小于或等于一个数的开方根的最大素数,e.x : 100 上限值为 7.
private static int determineIterationLimit() {
double iterationLimit = Math.sqrt(isCrossed.length);
return (int)iterationLimit;
}
//根据boolean数组中的标记,填充结果质数数组.
private static void loadPrimes() {
result = new int[numberOfUncrossedIntegers()];
for (int j = 0, i = 2; i < isCrossed.length; i++)
{
if (notCrossed(i))
{
result[j++] = i;
}
}
}
//返回所有质数的个数
private static int numberOfUncrossedIntegers() {
int count = 0;
for (int i = 2; i < isCrossed.length; i++)
{
if (notCrossed(i))
{
count++;
}
}
return count;
}
private static void initializeSieve(int maxValue) {
//初始化boolean数组,默认值为false,表数字没有被过滤掉.
//0,1不会被访问到.
isCrossed = new boolean[maxValue + 1];
for (int i = 2; i < isCrossed.length; i++)
{
isCrossed[i] = false;
}
}
}
分享到:
相关推荐
如果一段代码在多个地方重复,那么将其封装到一个单独的方法中是个好主意,这有助于减少代码重复和提高可维护性。例如: 原始代码: ```java public boolean isStartAfter(Date date) {...} public boolean ...
首先,重构应该是一个持续的过程,而不是一次性的大工程。其次,应该保持频繁的测试,确保代码重构不会引入新的错误。重构还应该采取小步快跑的方式,每次只进行少量改动,并且频繁地进行代码审查和测试,从而确保...
书中通过许多实际例子,详细说明了数据库重构的过程、策略以及部署。. 本书前5章介绍了演进式数据库开发的基本思想和技术,后6章详细描述了每一类重构,包括结构、数据质量、参照完整性、架构、方法的重构;另外还...
在C#编程中,窗体重构是一个常见的任务,它涉及到改变窗体的外观和行为以满足特定需求。本文主要探讨如何实现自定义窗体的皮肤重构,通过图文并茂的方式和真实例子帮助开发者掌握这一技能。 首先,我们需要设计一套...
以下是一个处理 Java 异常的例子: ```java try { // ⑸ Statement stat = conn.createStatement(); ResultSet rs = stat.executeQuery( "select uid, name from user"); while (rs.next()) { out.println(...
而均匀噪声则是在一个特定范围内随机取值,它的每个像素的值可能在设定的最小值和最大值之间变化,常用来模拟量化误差或其他不均匀的干扰。 在噪声污染后,我们使用小波变换进行图像恢复。小波变换是一种多分辨率...
这是一种创建型设计模式,它定义了一个创建对象的接口,但允许子类决定实例化哪一个类。这种将对象的创建延迟到子类的行为使得系统更加灵活,易于扩展。在本例中,我们将利用这个模式来构建计算器的不同操作,如加法...
1. **两顶帽子**(Two Hats):这是一种思维方式,意味着开发者需要同时具备两种视角——一个是作为开发者,另一个则是作为重构者。开发者负责编写新功能,而重构者则关注代码质量的提升。 2. **单元测试**(Unit ...
1-FFT(快速傅里叶变换)重构是全息图处理中的一个重要步骤,它在数字全息技术中扮演着核心角色。 在这个资源包中,包含了两个MATLAB程序——"离轴全息模拟.m"和"1-FFT重构.m",它们分别对应于离轴全息的模拟过程和...
在重构前的代码中,我们看到一个名为`LabelComparator`的类,它实现了`Comparator`接口并添加了`Serializable`特性。这个类包含了一个整型变量`sortType`用于表示排序方式(升序或降序)。`compare()`方法是`...
【描述】: 这是一个关于软件设计模式和重构的项目,具体是为西南科技大学的学生设计的心算大师游戏。游戏采用Java语言开发,运行于Windows平台,旨在提高用户的数学计算能力和思维敏捷度。游戏设有多种难度级别,并...
在上述文档内容中,作者通过设计一个媒体播放器的例子,逐步介绍了如何从面向过程的简单实现转换为面向对象的设计,并最终应用工厂模式和重构技巧,使得代码结构更加灵活和易于扩展。 在文档中提到了以下几点重要的...
**案例背景**:在一个项目中,系统的核心是一个类层次结构,其中存在大量的冗余代码和不合理的继承关系,导致维护困难。 **重构策略**: 1. **识别问题**:首先需要识别出代码中存在的问题,比如冗余的代码重复实现...
书中强调,一位经验丰富的程序员,可以运用重构技术,将一个看似复杂且难以维护的代码设计转化为一个清晰、高效的代码结构。 重构可以在很多方面进行,例如将代码从一个类转移到另一个类,或把某些代码提出来形成...
**发散式变化**:当一个类因为多种原因而频繁变化,应将其拆分为多个类,每个类负责一种变化。 **散弹式修改**:如果修改需要涉及大量类,可能表明设计问题,应将相关代码聚合到一个类中。 **依恋情结**:函数对...
可重构计算系统是一种新的实现计算系统的方法,它补充了原有通用处理器和专用硬件计算系统的不足,...在简单介绍可重构计算系统体系结构的基础上,通过一个嵌入式实时控制系统实例,给出了可重构计算系统的一种实现方法。
重构的过程涉及各种操作,比如将一个设计不佳的代码重构为设计良好的代码,把某个类中的代码移到另一个类,或者将一些代码提取出来形成一个新的函数。重构时,作者会指导读者何时找到机会进行重构,以及如何实施这些...
例如,工厂模式用于创建对象,观察者模式用于实现对象间的发布-订阅通信,单例模式则保证一个类只有一个实例。设计模式的应用可以提高代码的复用性,减少重复劳动,同时提升系统的可扩展性和灵活性。 在实际开发中...
目前哈特曼波前传感器波前重建的算法主要有两种,即区域波前重建法和模式波前重建法。...本资源给出了区域法重构算法实际例子, 资源具体内有以下资源: Slope_X.mat; Slope_Y.mat; 区域法重构.m 可直接运行!
1. **提取方法**:将一个长方法拆分成多个小方法,每个方法只做一件事情,这样可以提高代码的可读性和可复用性。 2. **移动函数/变量**:当发现函数或变量在错误的位置时,将其移动到更适合的地方,使得代码结构更...