问题描述
刚才看了一个招聘求100以内的质数问题,去求职的要求差不多都在7500/M以上,更有甚者要到12000/M,其实算法有很多种我贴出自己的算法,要价:4500/public static void main(String[] args) {for(int i=1;i<=100;i++){int flag = 0;for(int j=1;j<=i;j++){if(i%j==0){flag++;}}if(flag>2){continue;}else {System.out.println(i);}}} 问题补充:求一种计算执行所用时间的方法。
解决方案
用素数筛选(prime seive)是很快的,空间换时间,时间复杂度O(nlog(log(n)))public void runEratosthenesSieve(int upperBound) { int upperBoundSquareRoot = (int) Math.sqrt(upperBound); boolean[] isComposite = new boolean[upperBound + 1]; for (int m = 2; m <= upperBoundSquareRoot; m++) { if (!isComposite[m]) { System.out.print(m + " "); for (int k = m * m; k <= upperBound; k += m) isComposite[k] = true; } } for (int m = upperBoundSquareRoot; m <= upperBound; m++) if (!isComposite[m]) System.out.print(m + " ");}
解决方案二:
long span=System.currentTimeMillis();...执行程序...span=System.currentTimeMillis()-span;变量span就是你的程序执行的时间长度,单位毫秒
解决方案三:
在代码开始和结束各取一下系统时间,减一下就是代码的执行时间
解决方案四:
lz现在应该明白为啥人家要7500和12000了吧!4500和7500的差距啊!
解决方案五:
LZ的算法确实效率不高public static void main(String[] args) { for(int i=1;i<=100;i++){ //有必要每个数都去判断吗 int flag = 0; for(int j=1;j<=i;j++){//j不用判断到i为止吧到根号i就可以了,j也不用从1开始吧 if(i%j==0){ flag++;//j从2开始的话,整除了就直接break掉内层循环啊 } } if(flag>2){// 这里都可以省了。。 continue; }else { System.out.println(i); }}}
解决方案六:
import java.util.BitSet;public class PrimeNumber {//从end以内的素数private int end;//盛放标志位的容器private BitSet set;//构造方法public PrimeNumber(int end){this.end=end;this.set=new BitSet(end);}//把合数设置成trueprivate void conduct(){for (int i=2; i*i<=this.end; ++i){for (int j=2 ;j*i<=this.end; ++j){set.set(j*i);}}}//打印素数public void printScreen(){this.conduct();for(int i=1; i<=this.end; ++i){if(this.set.get(i)){continue;}else{System.out.println(i);}}}//测试代码public static void main(String[] args) {PrimeNumber prime=new PrimeNumber(1000);prime.printScreen();}}这是为你量身定做的,两样加起来,也许你可以要的更多点
解决方案七:
100以内的质数,数都数过来了。 不需要什么算法。
解决方案八:
空间占用少,但是速率不够快。
解决方案九:
不错