一小关羽求质数的程序 求人帮忙解释下

Question

int n= Math.sqrt(200);//求200以内的质数for(int i=1<;i<=n;i++)
{
       if(isPrime[i])//boolean类型的数组 大小等于200  如果其下标值是质数的话者该下标对应的值为true 反之为false
       {
           for(int j=i*2;j<=200;j+=i)
                   isPrime[j]=false;
        }
}学校12点断网了 明天有答案的就结贴给分 

Answer 1

所有小于200的非质数，最少可以分解为2个数的乘积，而且这两个数不可能都大于200的平方根。
所以，对于每一个小于200的平方根的数，将它的2倍，3倍直至N倍都设置为不是质数。这样遍历一次之后，剩下没被设置过到的就是质数
当然，这段程序是有小Bug的，按照这个思路，正确的能跑出结果的代码如下：
int n= (int)Math.sqrt(200);//求200以内的质数
boolean[] isPrime = new boolean[201]; for (int i=0; i<201; i++) {
isPrime[i] = true;
}

for(int i=2;i<=n;i++)
{
  //if(isPrime[i])//boolean类型的数组 大小等于200 如果其下标值是质数的话者该下标对应的值为true 反之为false
  for(int j=i*2;j<=200;j+=i)
  isPrime[j]=false;
}

for (int i=0; i<200; i++) {
if (isPrime[i]) System.out.println(i);
}

Answer 2

楼上的方法不错
还有个素数筛法时间复杂度能达到O(n)的
楼主可以自己搜下
主要思想就是合数都能分解成素数乘积
所以在小素数被求出来的时候可以组合成大些的合数将其pass掉

Answer 3

如果一个数N不是质数，必有2<= p <= sqrt(N)满足 N = p * q.