Loading... ## 欧几里得辗转相除法 $gcd(a, b)=gcd(b,a\ mod\ b)=···=gcd(n,0)$ ```c++ int gcd(int a, int b){ return b ? gcd(b, a % b) : a; } ``` ## 欧拉质数筛 #### 时间复杂度$O(n)$ ```c++ const int N = 1e8 + 10; int p[N], cnt; bool st[N]; void get_primes(int n){ for(int i = 2; i <= n; i++){ if(!st[i]) p[cnt++] = i; for(int j = 0; i * p[i] <= n; j++){ st[p[j] * i] = true; if(i % p[j] == 0) break; } } } ``` Last modification：January 10, 2023 © Allow specification reprint Like 0 如果觉得我的文章对你有用，请随意赞赏
Comment here is closed