素数搜索关键步骤与核心代码分析
:public abstract class AbstractPrimeFinder {//素数的判断过程pu
blic boolean isPrime(final int number){if(number <= 1)
return false;for(int i=2;i<=Math.sqrt(number);i++)if(nu
mber % i==0) return false;return true;}//计算一个区间内的素数的个数p
ublic int countPrimesInRange(final int lower,final int
upper){int total=0;for (int i=lower;i<=upper;i++)if(isP
rime(i)) total++;return total;}//统计程序计算素数所花费的时间public v
oid timeAndCompute(final int number){final long start =
System.nanoTime();final long numberOfPrimes = countPri
mes(number);final long end = System.nanoTime();System.o
ut.printf("Number of primes under %d is %d\n",number,nu
mberOfPrimes);System.out.println("Time (seconds) taken
is:"+(end-start)/1.0e9);}//子类继承实现的抽象方法public abstract i
nt countPrimes(final int number);}在AbstractPrimeFinder基
类中,将素数的寻找过程拆分为素数的判断(isPrime方法)、区间素数的寻找(countPrimesInRan
ge方法)和统计程序寻找最大素数的时间消耗(timeAndCompute方法)。countPrime()方法被
声明为abstract类型,用作素数寻找的入口方法,需要不同的子类进行覆盖实现,不同的执行方式将在此方法中定义
。在timeAndCompute()方法中,调用了此时被声明为abstract类型的countPrimes()
方法,这是面向对象程序设计中一条比较重要的设计方法。SinglePrimeFinder是素数寻找的普通版本,默
认情况下都是基于单线程的方式来执行的。其核心代码实现如下:public class SingleThreadP
rimeFinder extends AbstractPrimeFinder {// 实现父类中的方法@Ove
rridepublic int countPrimes(int number) {return this.co
untPrimesInRange(1, number);}//程序主方法public static void
main(String[] args) {new SingleThreadPrimeFinder().time
AndCompute(30000000);}}在此单线程版本中,countPrimes()方法接收number
参数作为搜索区间的上限,直接调用在基类中声明定义的countPrimesInRange()方法,基于1~num
ber进行素数的搜寻。在main()方法中创建SingleThreadPrimeFinder类的实例,并调用t
imeAndCompute()方法。启动素数的搜寻,并记录其中消耗的时间。在timeAndComputer()
方法中将基于面向对象技术中的多态方式调用countPrimes()方法,从而执行真正的搜寻操作。Concurr
entPrimeFinder实现了素数寻找的多线程版本,其核心代码实现如下:public class Conc
urrentPrimeFinder extends AbstractPrimeFinder {private
final int poolSize;//创建线程池的大小private final int numberOf
Parts;//任务的份数//构造方法初始化线程的个数和任务的划分public ConcurrentPrime
Finder(final int poolSize, final int numberOfParts) {th
is.poolSize = poolSize;this.numberOfParts = numberOfPar
ts;}@Overridepublic int countPrimes(final int number) {
int count=0;//统计各区间的素数个数try {final List> partitions = n
ew ArrayList>();final int chunksPerPartion=number /numb
erOfParts;for(int i=0; ifinal int lower = (i*chunksPerP
artion)+1;final int upper = (i==numberOfParts-1)? numbe
r:lower+chunksPerPartion-1;partitions.add(new Callable(
) {@Overridepublic Integer call() {return countPrimesIn
Range(lower,upper);}});}final ExecutorService executorP
ool = Executors.newFixedThreadPool(poolSize);//在线程池中创建线
程final List> resultFromParts = executorPool.invokeAll(p
artitions,10000,TimeUnit.SECONDS);executorPool.shutdown
();//执行完成之后关闭线程池for(final Future result:resultFromParts
)//统计各任务的素数个数count += result.get();}catch (Exception ex
){throw new RuntimeException(ex);}return count;}//启动4个线
程,4个分组方式来计算public static void main(String[] args){new C
oncurrentPrimeFinder(4,4).timeAndCompute(30000000);}}Co
ncurrentPrimeFinder类中定义了两个属性。poolSize用来定义线程池的大小,表示在程序中可
以并发执行的线程数量。numberOfParts定义了素数搜寻的区间数量。例如,搜寻区间为10 000,设置n
umberOfParts为4,则会生成0~2 500、2 501~5 000、5 001~7 500和7 50
1~10 000 4个搜寻的子区间。这些划分的好处在于,可以充分发挥当前硬件中多线程的优势。将各个区间的搜寻并
发处理,可以极大地提升整个程序的搜寻效率,缩短消耗的时间。类中声明了构造方法ConcurrentPrimeFi
nder()。其中,poolSize和numberOfParts作为入口参数,在构造方法中赋值给实例的对应属性
。countPrime()方法中定义了基于多线程技术实现的素数搜寻过程。在方法实现中,首先声明List的列表结
构,用于存放拆分之后的具体线程任务。Callable是Java语言实现线程并返回结果值的一种实现方式。搜寻素数
的过程根据区间数量进行拆分,并将每一个子区间封装到Callable的对象之内,同时将Callable对象放入L
ist的列表之内。基于Executors工具类声明了poolSize大小的执行线程池。调用线程池executo
rPool的invokeAll()方法,执行List列表中存放的Callable线程任务。在线程池执行完毕,调
用shutdown()方法,关闭线程池。遍历线程池执行的结果resultFromParts,并将其中的结果进行
累计,得到最终的素数个数。在整个执行过程中,线程池存在异常发生的可能,需要进行异常的捕获。这里使用try…ca
tch进行异常的捕获。当异常发生时,将异常栈的信息输出到控制台。对于线程池中的异常,在当前方法中无法处理,于是
创建新的RuntimeException,抛出给调用者,交由调用者根据具体情况来处理。在main()方法中,创
建ConcurrentPrimeFinder实例,指定poolSize为4,素数搜索区间为4,在1~30 00
0 000区间中搜寻存在的素数数量。在此多线程版本中,使用了ExecutorService类型的线程池。基于E
xecutors的线程创建方式和Callable的线程实现方式。此案例是将一个大的执行区间拆分为了若干个彼此独
立的子区间,并将它们分别放入Callable的线程实现中。