\(prime\)
const int N = 1e7+10;
int prime[N];
bool notprime[N];
int minprime[N];
void prime_sieve(const int maxn) {
register int i, multi_helper;
register int* j;
const int half_maxn = maxn>>1;
for(i = 2;i <= half_maxn;++i) {
if(!notprime[i]) {
prime[++prime[0]] = i;
minprime[i] = i;
}
for(j = prime+1;*j&&*j <= minprime[i];++j) {
notprime[i*(*j)] = true;
minprime[i*(*j)] = *j;
}
}
for(;i <= maxn;++i)
if(!notprime[i]) {
prime[++prime[0]] = i;
minprime[i] = i;
}
}
const int N = 1e8+5e7+10;
const int P = 1e7+10;
int prime[P];
int minprime[N];
void prime_sieve(const int maxn) {
register int i, upd;
register int* j;
const int half_maxn = maxn>>1;
for(i = 2;i <= half_maxn;++i) {
if(!minprime[i]) {
prime[++prime[0]] = i;
minprime[i] = i;
}
upd = std :: min(maxn/i,minprime[i]);
for(j = prime+1;*j&&*j <= upd;++j)
minprime[i*(*j)] = *j;
}
for(;i <= maxn;++i)
if(!minprime[i])
prime[++prime[0]] = i;
}
这个常数还是比较小的。
可以在 \(80\ ms\) 内处理出 \(1e7\) 以内的素数。
可以在 \(0.8\ s\) 内处理出 \(1e8\) 以内的素数。
\(upd\ on\ 2022.10.07\)
const int N = 100000005;
const int P = 30000005;
int prime[P];
int *p = prime;
int minprime[N];
void tree_line(int max_size) {
const int half_size = max_size>>1;
const int tree_size = max_size/3;
const int sqrt_size = sqrt(max_size);
int i, upd;
int *j;
minprime[2] = minprime[4] = *++p = 2;
for(i = 3;i <= sqrt_size;++i) {
if(!minprime[i])
*++p = minprime[i] = i;
for(j = prime+1;;++j) {
minprime[i*(*j)] = *j;
if(*j == minprime[i])
break;
}
++i;
minprime[i<<1] = 2;
}
for(;i <= tree_size;++i) {
if(!minprime[i])
*++p = minprime[i] = i;
if((upd = max_size/i) >= minprime[i]) {
for(j = prime+1;*j <= minprime[i];++j) {
minprime[i*(*j)] = *j;
if(j == p)
break;
}
} else {
for(j = prime+1;*j <= upd;++j) {
minprime[i*(*j)] = *j;
if(j == p)
break;
}
}
++i;
minprime[i<<1] = 2;
}
for(;i <= half_size;++i) {
if(!minprime[i])
*++p = minprime[i] = i;
minprime[i<<1] = 2;
++i;
minprime[i<<1] = 2;
}
for(;i <= max_size;i += 2)
if(!minprime[i])
*++p = i;
}
这份板子在电脑稳定情况下，筛 \(1e8\) 仅需 \(465\,ms\) 左右。（-O2）
其中加入了对：
-
\(\sqrt n\) 的讨论
-
\(\frac{n}{3}\) 的讨论
-
\(\frac{n}{2}\) 的讨论
-
奇偶性的讨论
下一步准备搞数论分块，降低除法次数。
\(\varphi(n)\)
ull phi[z];
void line_phi(int n) {
b.reset();
phi[1] = 1;
for(int i = 2;i <= n;++i) {
if(!b[i]) {
prime[++prime[0]] = i;
phi[i] = i-1;
}
for(int j = 1;j <= prime[0];++j) {
if(i*prime[j] > n) break;
if(i%prime[j])
phi[i*prime[j]] = phi[i]*phi[prime[j]];
else {
phi[i*prime[j]] = phi[i]*prime[j];
break;
}
}
}
}
\(\mu(n)\)
int mu[z];
void line_mu(int n) {
b.reset();
mu[1] = 1;
for(int i = 2;i <= n;++i) {
if(!b[i]) {
mu[i] = -1;
prime[++prime[0]] = i;
}
for(int j = 1;j <= prime[0];++j) {
if(i*j > n) break;
b[i*prime[j]] = 1;
if(i%prime[j] == 0) {
mu[i*prime[j]] = 0;
break;
}
mu[i*prime[j]] = -mu[i];
}
}
}
开始卡常。
const int N = 1e7+10;
const int P = 4e6+10;
int mu[N];
int minprime[N];
int prime[N];
void init(int init_size) {
const int half_size = init_size>>1;
register int i, *j, upd, m_h;
register int *p = prime+1;
mu[1] = 1;
for(i = 2;i <= half_size;++i) {
if(!minprime[i]) {
minprime[i] = i;
*p++ = i;
mu[i] = -1;
}
if((upd = init_size/i) >= minprime[i]) {
for(j = prime+1;*j < minprime[i];++j) {
minprime[m_h = i*(*j)] = *j;
mu[m_h] = -mu[i];
}
minprime[m_h = i*(*j)] = *j;
mu[m_h] = 0;
} else {
for(j = prime+1;*j <= upd;++j) {
minprime[m_h = i*(*j)] = *j;
mu[m_h] = -mu[i];
}
}
mu[i] += mu[i-1];
}
for(;i <= init_size;++i)
if(!minprime[i])
mu[i] = mu[i-1]-1;
else
mu[i] += mu[i-1];
}
可以稳定在 \(128\,ms\) 左右，不错了。
注意卡常的板子筛的是 \(mu(n)\) 的前缀和。
\(\tau(n)\)
ull tau[z];
ull num[z];
void line_tau(int n) {
tau[1] = 1;
for(int i = 2;i <= n;++i) {
if(!b[i]) {
b[i] = 1;
prime[++prime[0]] = i;
tau[i] = 2;
num[i] = 1;
}
for(int j = 1;j <= prime[0];++j) {
if(i*prime[j] > n) break;
b[i*prime[j]] = 1;
if(i%prime[j] == 0) {
num[i*prime[j]] = num[i]+1;
tau[i*prime[j]] = tau[i]/num[i*prime[j]]*(num[i*prime[j]]+1);
break;
} else {
num[i*prime[j]] = 1;
tau[i*prime[j]] = tau[i]*2;
}
}
}
}
\(\sigma(n)\)
ull sigma[z];
ull g[z];
void line_sigma(int n) {
sigma[1] = g[1] = 1;
for(int i = 2;i <= n;++i) {
if(!b[i]) {
b[i] = 1;
prime[++prime[0]] = i;
g[i] = i+1;
sigma[i] = i+1;
}
for(int j = 1;j <= prime[0];++i) {
if(i*prime[j] > n) break;
b[i*prime[j]] = 1;
if(i%prime[j] == 0) {
g[i*prime[j]] = g[i]*prime[j]+1;
sigma[i*prime[j]] = sigma[i]/g[i]*g[i*prime[j]];
break;
} else {
sigma[i*prime[j]] = sigma[i]*sigma[prime[j]];
g[i*prime[j]] = 1+prime[j];
}
}
}
}