21天零基础入门ACM

21天零基础入门ACM之 第19天

欧拉筛

欧拉筛

欧拉筛就是用来线性筛素数的一种算法。
素数就是除了1和本身，没有其他的因数的数。

埃氏筛

首先先介绍一下埃氏筛，埃氏筛是思路就是先把所有的数都当成素数。
从2开始吧，2的倍数全置为非素数。
下一步，3没被筛掉，所以把3的倍数全筛掉。
下一步，4被筛掉了，跳过4。
下一步，5没被筛掉，所以把5的倍数全筛掉。
一直重复，剩下的就是素数。

时间复杂度o(n*n);
代码：

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int n,m;
const int N=1e5+7;
int nums[N];
vector<int>prime;

void is_prime(){
	for(int i=2;i<=N;i++){
		if(nums[i]==0){
			prime.push_back(i);
		}
		for(int j=2;i*j<=N;j++){
			nums[i*j]=1;
		}
	}
} 

int main() {
	is_prime();
	for(int i=0;i<10;i++) cout<<prime[i]<<" ";
	return 0;
}

欧拉筛

想想6，是不是被2筛掉了一次，又被3筛掉了一次。
怎么样可以让一个数，只被筛掉一次呢？
这就是欧拉筛法。
代码：

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define sc(x) scanf("%d",x)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    
ll qpow(ll a, ll b, ll mod) { ll ans = 1;  a%=mod; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

const int mod=1e9+7;
const int N=1e7+7;

ll prime[N],cnt=1;
bool st[N];

void is_prime() {
    memset(st, true, sizeof(st));
    for (int i = 2; i <= N; i++) {
        if (st[i])
            prime[cnt++] = i;
        for (int j = 1; prime[j] * i <= N; j++) {
            st[prime[j] * i] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
}

int main() {
    is_prime();
    for (int i = 1; i < 30; i++)
        cout << prime[i] << " ";
}

例题：

例题1：https://ac.nowcoder.com/acm/contest/11214/H


代码：

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define sc(x) scanf("%d",x)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    
ll qpow(ll a, ll b, ll mod) { ll ans = 1;  a%=mod; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

const int mod=1e9+7;
const int N=1e8+7;

ll prime[N],cnt=1;
int st[N];
int ans[N];

void is_prime() {
    memset(st, true, sizeof(st));
    for (int i = 2; i <= N; i++) {
        if (st[i])
            prime[cnt++] = i;
        for (int j = 1; prime[j] * i <= N; j++) {
            st[prime[j] * i] = false;
            if (i % prime[j] == 0)
                break;
        }
    }
}
int t,l,r;
int main() {
    is_prime();
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=5761456;i++){
    	for(int j=1;j<=5761456;j++){
    		ll x=prime[i]*prime[j];
    		if(x>1e8) break;
    		else if(st[x]==false) st[x]=2;
		}
	}
	for(int i=0;i<=N;i++){
		if(st[i]!=2) ans[i]=ans[i-1];
        else ans[i]=ans[i-1]+1;
	}
    cin>>t;
    while(t--){
        cin>>l>>r;
        cout<<ans[r]-ans[l-1]<<endl;
    }
    return 0;
}

例题2：https://ac.nowcoder.com/acm/contest/12478/E


代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll maxn = 1e7+5;
ll prime[maxn], i, j, countnum = 1;
bool num[maxn];
void oula(ll n)
{
    memset(num, true, sizeof(num));
    for (i = 2; i <= n; ++i) { 
        if (num[i]) prime[countnum++] = i;
        for (j = 1; j < countnum; ++j) {
            if (i*prime[j] > n) break; 
            num[i*prime[j]] = false;  
            if (i%prime[j] == 0) break; 
        }
    }
}

ll ksm(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans%mod;
}
 
int main()
{
    oula(maxn);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n=0,m,a;
        cin>>a;
        m=a*(a-1)/2;
        for(ll k=2;prime[k]<=a;k++)
        {
            if(prime[k]==prime[k-1]+2)
            n++;
        }
        cout<<(n*ksm(m%mod,mod-2))%mod<<endl;
    }
    return 0;
}