lihong082871
2011-04-11 17:36
浏览 327
已采纳

求100以内的质数,值得一看

刚才看了一个招聘求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);
}
}
}

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

9条回答 默认 最新

  • fivestaralex 2011-04-11 23:30
    已采纳

    用素数筛选(prime seive)是很快的,空间换时间,时间复杂度O(nlog(log(n)))
    [code="java"]
    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 + " ");
    }
    [/code]

    已采纳该答案
    打赏 评论
  • wenchenyang 2011-04-11 19:09

    不错

    打赏 评论
  • turing-complete 2011-04-11 19:21

    空间占用少,但是速率不够快。

    打赏 评论
  • iteye_5430 2011-04-11 19:35

    100以内的质数,数都数过来了。
    不需要什么算法。

    打赏 评论
  • turing-complete 2011-04-11 20:35

    [code="java"]
    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);
    }
    //把合数设置成true
    private 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();
    }
    

    }
    [/code]
    这是为你量身定做的,两样加起来,也许你可以要的更多点

    打赏 评论
  • redstarofsleep 2011-04-11 22:20

    LZ的算法确实效率不高
    [code="java"]
    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);
    }
    }
    }
    [/code]

    打赏 评论
  • ethenjean 2011-04-12 09:46

    lz现在应该明白为啥人家要7500和12000了吧!4500和7500的差距啊!

    打赏 评论
  • redstarofsleep 2011-04-12 09:54

    在代码开始和结束各取一下系统时间,减一下就是代码的执行时间

    打赏 评论
  • turing-complete 2011-04-12 10:13

    [code="java"]
    long span=System.currentTimeMillis();
    ...执行程序...
    span=System.currentTimeMillis()-span;
    [/code]

    变量span就是你的程序执行的时间长度,单位毫秒

    打赏 评论

相关推荐 更多相似问题