订阅业界RSS CSDN首页> 业界

第四期POWER8大赛算法分析:非质数筛选法

发表于2015-04-15 15:59| 次阅读| 来源未知| 0 条评论| 作者李洪亮

摘要:由CSDN和IBM联合举办的2014 Power 8极限性能挑战赛 自正式启动以来,受到了许多编程爱好者及程序员们的关注。该大赛以云计算的方式为开发者提供了Power 8开发环境,开发者将利用Power 8的特性,基于不同场景进行应用开发。 此次大赛主要面向广大CSDN注册开发者,大赛以云计算的方式为开发者提供了Power 8开...

由CSDN和IBM联合举办的“2014 Power 8极限性能挑战赛”自正式启动以来,受到了许多编程爱好者及程序员们的关注。该大赛以云计算的方式为开发者提供了Power 8开发环境,开发者将利用Power 8的特性,基于不同场景进行应用开发。

此次大赛主要面向广大CSDN注册开发者,大赛以云计算的方式为开发者提供了Power 8开发环境,开发者利用Power 8的特性,基于不同场景进行应用开发。此次大赛,不仅使更多的开发者充分利用了Power 8,也为开发者、技术达人提供一个展示自我的舞台。

Power 8极限性能挑战赛已成功举办三期。(第一期“博客反垃圾”、第二期“敏感词大文本过滤”第三期“文章TOP 100”)。现在,我们又迎来了极限算法挑战赛第四期本期挑战赛的题目是“计算质数”,具体任务由用户自由输出1-10亿内所有质数。需要说明的是,大赛主要考察程序的是算法的正确率及处理速度,对开发语言、开发工具并不进行限定。

到目前为止,已经有数百名开发者报名并参加了POWER8大赛,为了让更多的开发者深入了解大赛的运算技巧。经Power8大赛组委会邀请,第四期POWER8大赛参赛者周一峰将作对其提交的算法进行剖析。

此次,周一峰最终算法时间为11.93s,以下是具体分析内容:

对于“计算质数”这一题目,周一峰主要运用筛选方式设计的算法,具体算法是将1到10亿个数字整理到文档里,然后排除非质数,剩余数字便是质数。

那么如何才能排除掉非质数呢?首先,我们需要考虑的是任何一个非质数,都是一个质数和另一个数字的乘积。所以,只要把质数分别乘以每一个数字,最终得出的结果便是非质数。

说到这里,大家可能会问到,究竟需要用多少质数去乘积?乘积的数字需要到多大为止?本期大赛目的是筛选1到10亿数内所有质数。所以,选取质数是根号10以下即可,之后每次乘积的数字都增加1,一直乘积超过10亿为止。(10亿以内所有非质数,他的因数肯定是有一个会小于或等于根号10亿的,所以用根号10亿下的所有质数分别去乘以各个数字,就可以表示出10亿以下的所有非质数了。)

据了解,周一峰主要从事.NET WEB后端和hadoop大数据开发工作,一般情况下,开发环境基本都在PC上完成,处理器也属于非企业级。对于此次体验POWER8服务器周一峰说:“参加此次Power8大赛,让我有幸切身体验服务器CPU性能的机会,同时也加深对POWER8服务器的了解。我们都知道POWER8每个核心都有8线程技术,我在大赛编码过程中使用这项技术,提高程序运行效率。但据我测试,使用多线程相比单核心的性能可以提高2到3倍。”

周一峰算法展示:

import java.io.BufferedWriter;

import java.io.File;

import java.io.FileOutputStream;

import java.io.IOException;

import java.io.OutputStreamWriter;

public class csdn {

public static void main(String[] args) throws IOException {

String path=args[0];

File fileAllPrime=new File(path);

FileOutputStream fosAllPrime=new FileOutputStream(fileAllPrime);

OutputStreamWriter oswAllPrime=new OutputStreamWriter(fosAllPrime);

BufferedWriter bwAllPrime=new BufferedWriter(oswAllPrime);

boolean[]  isNotPrimeArr=new boolean[500000000];

isNotPrimeArr[0]=true;

double sqrt=(Math.sqrt(1000000000)-1)/2;

bwAllPrime.write(2+"\r\n");

int primeCount=1;

for(int a=1;a<=sqrt;a++)

{

boolean isNotPrime=isNotPrimeArr[a];

if(!isNotPrime)

{

int prime=a*2+1;

bwAllPrime.write(prime+"\r\n");

primeCount++;

int i=3;

int notPrime=prime*i;

while(notPrime<=1000000000)

{

isNotPrimeArr[(notPrime-1)/2]=true;

i=i+2;

notPrime=prime*i;

}

}

}

for(int a=(int) (sqrt+1);a<isNotPrimeArr.length;a++)

{

boolean isNotPrime=isNotPrimeArr[a];

if(!isNotPrime)

{

primeCount++;

int prime=a*2+1;

bwAllPrime.write(prime+"\r\n");

}

}

bwAllPrime.close();

oswAllPrime.close();

fosAllPrime.close();

System.out.println("primeCount:"+primeCount); 

}

0
0