记录LeetCode204

昨天闲来无事刷了道LeetCode计算质数这道题，看起来很简单，计算n以下有多少质数

我的代码是这样的，

class Solution
 {
    public int countPrimes(int n)
    {
     int sum=0;
     for(int i=1;i<n;i++)
     {
         if(isPrime(i))
            sum=sum+1;
     }
     return sum;
    }
    public boolean isPrime(int m)
    {   
        if(m==0 || m==1)
            return false;
        if(m==2)
            return true;
        for(int i=2;i<=Math.sqrt(m);i++)
        {
            if(m%i==0)
                return false;
        }
        return true;
    }
}

然后高高兴兴的先运行测试了一下，没问题，然后就去提交了，意料之中的事还是发生了，提交并未通过，超时了，然后我就去题解看了下，果然有很精妙的解法。

这位大兄弟的解法是最让人虎躯一震的，直接把全部的测试用例列了出来，时间复杂度还是O(1)，斜眼笑.jpg。

class Solution
{
public int countPrimes(int n)
{
if(n==10)
    return 4;
else if(n==3)
    return 1;
else if(n==4)
    return 2;
else if(n==5)
    return 2;
else if(n==6)
    return 3;
else if(n==7)
    return 3;
else if(n==8)
    return 4;
else if(n==9)
    return 4;
else if(n==11)
    return 4;
else if(n==12)
    return 5;
else if(n==13)
    return 5;
else if(n==14)
    return 6;
else if(n==16)
    return 6;
else if(n==15)
    return 6;
else if(n==10000)
    return 1229;
else if(n==499979)
    return 41537;
else if(n==999983)
    return 78497;
else if(n==1500000)
    return 114155;
else
    return 0;
}
}

说到正题上来，最优解法应该是厄拉多筛选法：

public int countPrimes(int n)
{
    int[] nums = new int[n];
    for (int i = 0; i < n; i++)
    {
        nums[i] = 1;
    }
    for (int i = 2; i < n; i++)
    {
        if (nums[i] == 1)
        {
            for (int j = 2; i * j < n; j++)
            {
                nums[i * j] = 0;
            }
        }
    }
    int res = 0;
    for (int i = 2; i < n; i++)
    {
        if (nums[i] == 1)
            res++;
    }
    return res;
}

厄拉对筛选法用空间换了时间，开辟了一个长度为n大小的数组。

如求10之内的质数，首先列出2~9的所有数，如果当前数为质数，则其倍数就是质数

如第一个质数为2，在2上画圈，其倍数4/6/8不是质数，划掉4/6/8，继续遍历

• 下一个质数为3，在3上画圈，其倍数6/9不是质数，划掉6/9，继续遍历
• 下一个质数为5，在5上画圈，没有倍数，继续遍历
• 下一个质数为7，在7上画圈，没有倍数，继续遍历
• 最后再次遍历整个数组，画圈的数字就是质数，即2,3,5,7

转换为代码就是如果需要求<n的所有质数个数，则创建一个长度为n的整数数组，所有元素值变为1，1表示对应的索引值为质数，0表示对应的索引值为非质数。从2开始遍历，如果当前数字值为1，则获取其所有倍数，将元素值变为0（标记为非质数）。遍历完成后再次遍历数组，从2开始，记录元素为1的个数，即为对应的质数个数。