《质数》判断质数（较快的方法C++）_c++ 判断质数时间复杂度

前言

  to be honest，我感觉我也刷了1,200道题了，真是有的题刷了一次又一次，但是还是存在会的还是会，不会的还是不会。因而我就思考是不是我的做题模式出现了问题。下面展示一下我之前的做题风格，

哎，还是走高三的老路，就是刷题，不总结，不分类，只追求数量。为了改善这种情况，我决定做好总结与分类，以求有所进步。

正题：

bool isPrime(int a) {
    if(a == 1) return 0;
    if(a == 2 || a == 3) return 1;
    if(a%6 != 1 && a%6 != 5) return 0;
    int sqrtA = sqrt(a);
    for(int i = 5; i <= sqrtA; i += 6) {
        if(!(a%i)|| !(a%(i+2))) return 0;
    }
    return 1;
}

  思路解析：规律就是把大于等于5数按%6分类，会有余数为0 ,1,2,3,4,5共6种情况，这六种情况中，0,2,3,4是不行的，有可以整除的数，只有1,5满足， 那么就对余数为1，5的这一类数记为A类进行判断，只要他们不被比自己小的A类的数整除，就可以说明这个数是质数。时间复杂度（sqrt（n）/3）相当于只用判断小于sqrt（n）的1/3的数。

思考：

  做事之前先思考大多数情况下都会很省时间！