题目传送门

sol1：普通判到sqrt(n)的素数判定，不多说了。

素数判定

#include "bits/stdc++.h"

using namespace std;

bool is_prime(int n) {

    for (int i = ; 1LL * i * i <= n; i++)

    {

        if (n % i == ) return false;

    }

    return true;

}

int main() {

    int n, m;

    while (~scanf("%d", &n)) {

        int cnt = ;

        for (int i = ; i <= n; i++) {

            scanf("%d", &m);

            if (is_prime(m)) cnt++;

        }

        printf("%d\n", cnt);

    }

    return ;

}

复杂度sqrt(m),判断n次就是n * sqrt(m);

sol2：新get到的技巧Miller-Rabin素数测试，结合了费马小定理和二次探测定理，可以更高效的判断素数，存在误判可能，不过误判可能非常小，可以忽略不计；

Miller-Rabin素数测试

#include "bits/stdc++.h"

using namespace std;

int quick_pow(int n, int k, int p) {

    int ans = ;

    while (k) {

        if (k & ) ans = 1LL * ans * n % p;

        n = 1LL * n * n % p;

        k >>= ;

    }

    return ans;

}

bool is_prime(int n) {

//    if (n < 2) return false;

    int s = , t = n - ;

    while (!(t & )) s++, t >>= ;

    for (int i = ; i <= ; i++) {

        int a = rand() % (n - ) + ;

        int k = quick_pow(a, t, n);

        for (int j = ; j <= s; j++) {

            int x = 1LL * k * k % n;

            if (x ==  && k !=  && k != n - ) return false;

            k = x;

        }

        if (k != ) return false;

    }

    return true;

}

int main() {

    int n, m;

    srand(time(NULL));

    while (~scanf("%d", &n)) {

        int cnt = ;

        for (int i = ; i <= n; i++) {

            scanf("%d", &m);

            if (is_prime(m)) cnt++;

        }

        printf("%d\n", cnt);

    }

    return ;

}

复杂度logm，判断n次就是n * log(m);

附加一个用于 LL 范围素数测试的模板：s

Miller-Rabin素数测试 LL 范围模板

typedef long long LL;

LL quick_mul(LL n, LL k, LL p) {

    LL ans = ;

    while (k) {

        if (k & ) ans = (ans + n) % p;

        n = (n + n) % p;

        k >>= ;

    }

    return ans;

}

LL quick_pow(LL n, LL k, LL p) {

    LL ans = ;

    while (k) {

        if (k & ) ans = quick_mul(ans, n, p);

        n = quick_mul(n, n, p);

        k >>= ;

    }

    return ans;

}

bool is_prime(LL n) {

    if (n < ) return false;

    LL s = , t = n - ;

    while (!(t & )) s++, t >>= ;

    for (int i = ; i <= ; i++) {

        LL a = rand() % (n - ) + ;

        LL k = quick_pow(a, t, n);

        for (int j = ; j <= s; j++) {

            LL x = quick_mul(k, k, n);

            if (x ==  && k !=  && k != n - ) return false;

            k = x;

        }

        if (k != ) return false;

    }

    return true;

}

大致差不多，为了防止爆 LL 加了一个快速积用于乘，所以复杂度变成了log(m) * log(m)

巴特西

HDU-2138-How many prime numbers(Miller-Rabin新解法)

题目传送门

最新文章

热门文章