求第100002个素数。(2是第一个素数)

 

结题思路:素数筛法

代码如下:

import java.util.Arrays;


public class Copy_2_of_Main {
    
    
static int N = 10000000;
    
static int count;
    
static int rs[] = new int[N];
    
static boolean tg[] = new boolean[N];//is prime
    
    
public static void main(String[] args) {
        
        Arrays.fill(tg, 
true);
        
int ed = (int)Math.sqrt(N) + 1;
        
for(int i = 2; i <= ed; i++){//素数筛法
            if(tg[i]){
                
for(int j = i * 2; j < N; j += i){// j += i
                    tg[j] = false;
                }

            }

        }

        count 
= 0;
        
for(int i = 2; i < N; i++){
            
if(tg[i] == true){
                rs[count
++= i;
            }

        }

        System.out.println(
"count=" + count);
        System.out.println(
"result=" + rs[100001]);
//        for(int i = 0; i < count; i++)
//            System.out.println(rs[i]);
    }

        
}


posted on 2013-07-06 19:38 小鼠标 阅读(157) 评论(0)  编辑 收藏 引用 所属分类: Java基础练习

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2013年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜