能不能帮我看看这个函数

Question

package je3.basics;
public class Sieve
{
public static void main(String[] args){
int max =100;
try{ max = Integer.parseInt(args[0]); }
catch (Exception e){}
boolean[] isprime = new boolean[max+1];
for(int i=0;i<=max;i++) isprime[i] = true;//先将所有值都默认为质数
isprime[0] = isprime[1] =false;//不是质数的话布尔值为false.
int n =(int) Math.ceil(Math.sqrt(max));//ceil函数 返回最小的（最接近负无穷大）double 值，该值大于等于参数，并等于某个整数。
//sqrt 返回正确舍入的 double 值的正平方根。
for(int i=0;i<=n;i++){
if (isprime[i])
{
for(int j= 2*i; j<=max;j=j+i)
isprime[j]=false;
}
}
int largest;
for(largest = max; !isprime[largest]; largest--);
System.out.println("largest prime less than or equal to "+ max + "is"+largest);
}
}
这其中for(int i=0;i<=n;i++)这个循环究竟做了什么，为什么就能分辨出质数了呢？能不能将详细一点。谢谢了～

Answer 1

 boolean[] isprime = new boolean[max+1];
        for(int i=0;i<=max;i++) isprime[i] = true;//先将所有值都默认为质数
这个循环你可以理解为初始化这个布尔类型的数组 全部设为true

Answer 2

不是这个循环，是后面那个for循环，将i*2=j,j=j+i全部设为非质数的循环

Answer 3

for(int i=0;i<=n;i++){
            if (isprime[i])
            {
                for(int j= 2*i; j<=max;j=j+i)
                    isprime[j]=false;
            }
        }你指的是这段代码吧，首先我们知道质数是指除了1和他本身不能被其他整数整除的数。前面假设了所有的数都是质数，我们只要把不是质数的全部去掉，剩下的就是质数。其中内部循环中初始设置为2i，每次加i，也就是把2i、3i、4i一直到ki（k为整数，ki<=max）排除，i的数值从2到n也就排除了，所有能被2到n整除的数。自然也就排除了n^2内所有的非质数，剩下的就是质数了。

Answer 4

你这个是筛法求素数吧，但筛法有线性筛噢~~
for (i = 2; i < max; i++) fact[i] = i;
for (i = 2; i < max; i++) {
if (fact[i] == i) p[m++] = i;
for (j = 0; j < m && p[j]*i < max && p[j] <= fact[i]; j++) 
fact[p[j]*i] = p[j];
}其中fact[i]表示i的最小质因子。

Answer 5

what is 线性筛？？？我很菜的。。能解释一下最好不过了。。

Answer 6

筛法判定素数的道理在于：每个合数会被它的质因数遍历到（在你的程序里，合数j被它的质因数i遍历到，因此isprime[j] = false）。但是每个合数有多个质因数，于是isprime[j] = false这句对每个j运行了不止一次，因此不是线性的。线性筛的好处就在每个合数只被他的最小质因数fact[i]遍历到，每个合数只判断一次，所以是线性的。
//p[m]储存1~max的所有素数
for (i = 2; i < max; i++) fact[i] = i;
for (i = 2; i < max; i++) {
    if (fact[i] == i) p[m++] = i;
    //如果最小质因数等于自身，那么i是素数
    for (j = 0; j < m && p[j]*i < max && p[j] <= fact[i]; j++) 
        fact[p[j]*i] = p[j];
    //注意p[j]<=fact[i]，因此p[j]*i的最小素因数为p[j]
}可以去google“线性筛法”

Answer 7

可以去看看这个的讲解
http://blog.csdn.net/bjrxyz/article/details/8125913