解法

第一个问题需要考虑如何单纯的判断一个数字是否是素数
第二个问题就是如何加速for循环的判断

问题1

public boolean isP(int num)
    {
        for(int i=2;i*i<=num;i++)
        {
            if(num%i==0) return false;
        }
        return true;
   }

问题2

 public int countPrimes(int n) {

        boolean[] res=new boolean[n];
        Arrays.fill(res,true);//最开始默认都是素数
        for(int i=2;i*i<n;i++)
        {
            //判断当前是否是素数
            if(isP(i))  
            {
                for(int j=i*i;j<n;j+=i)
                {
                    res[j]=false;
                }
            }
        }
        int count=0;
        for(int i=2;i<n;i++)
        {
            if(res[i]) count++;
        }
        return count;
    }

总结

考虑到质数就要考虑到开根和平方