18图灵班作业6--LeetCode编程题

先是普通筛法

class Solution {
public:
    int countPrimes(int num) {
        int ans=0;
        bool* NotPrime=new bool[1500000+5];
        NotPrime[1]=1;
        NotPrime[2]=0;
        NotPrime[3]=0;
        for(int i=2;i<num;i++){
            if(NotPrime[i]) continue;
            for(int j=i+i;j<num;j+=i){
                NotPrime[j]=1;
            }
        }
        for(int i=1;i<num;i++){
            if(!NotPrime[i]) ans++;
        }
        return ans;
    }
};

首先筛法是离线算法，用在这类批量查询的题上肯定是有很大优势的。
然后尝试着写了一下米勒拉宾。

class Solution {
typedef long long LL;
public:
    LL QuickPower(LL a,LL b,LL n){
        LL res=1;LL base=a;
        while(b>0){
            if(b&1) res=(res*base)%n;
            base=(base*base)%n;
            b>>=1;
        }
        return res;
    }
    bool MillerRabbin(int n,int a){
        int r=0,s=n-1;
        if(!n%a) return false;
        while(!(s&1)){
            r++;
            s>>=1;
        }
        LL k=QuickPower(a,s,n);
        if(k==1) return true;
        for(int j=0;j<r;j++,k=(k*k)%n){
            if(k==n-1) return true;
        }
        return false;
    }
    bool IsPrime(int n){
        int a[]={2,7,61};
        for(int i=0;i<3;i++){
            if(n==a[i]) return true;
            if(!MillerRabbin(n,a[i])) return false;
        }
        return true;
    }
    int countPrimes(int num) {
        int ans=0;
        for(int i=2;i<num;i++){
            if(IsPrime(i)) ans++;
        }
        return ans;
    }
};

结果是超时。
本地run code 是700ms+，但submit就是tle.
然后我试着把a改成只用2,5两个，还是超时。（本地测试答案是正确的）
也试着把k=(k*k)%n这类的改写成快速幂，特判可以直接整除的情况，还是超时。
老师有空的话帮我看看，是我的实现方式过于低效了吗？