筛法和欧拉函数

简介

欧拉函数: 小于n的正整数中与n互质的数的数目 筛法: 埃氏筛, 快速找到小范围(1~1e7)内的素数

---

欧拉函数

//欧拉函数打表
const int MAX=3000001;
long long e[MAX];
void geta()
{
    e[1]=0;
    for(int i=2;i<MAX;++i)
        e[i]=i;
    for(int i=2;i<MAX;++i)
        if(e[i]==i)
            for(int j=i;j<MAX;j+=i)
                e[j]=e[j]/i*(i-1);
 
    for(int i=2;i<MAX;++i)//去掉这句话,e[i]表示i的欧拉值
        e[i]+=e[i-1];
}
//e[i]表示从1到i每个数欧拉值的总和
 
int euler(int n)//返回一个数的欧拉值
{
    int res=n,a=n;
    for(int i=2; i*i<=a; i++)
    {
        if(a%i==0)
        {
            res=res/i*(i-1);
            while(a%i==0) a/=i;
        }
    }
    if(a>1) res=res/a*(a-1);
    return res;
}

区间筛法

#include<iostream>//区间筛法
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define M 65538
#define LL long long
const int maxn=1000001;//区间长度最大值
bool visit[M];
bool is[maxn];
int ans[maxn];
LL p[M];
int cnt=0;
void iii()//找2~sqrt(INF)的素数,65537是素数且大于sqrt(2^31-1);
{
    memset(visit,true,sizeof(visit));
    visit[1]=0;
    for(long long i=2; i<M; ++i)
    {
        if(visit[i]==true)
        {
            p[cnt++]=i;
            for(long long  j=i*i; j<M; j+=i)
            {
                visit[j]=false;
            }
        }
    }
}
//区间筛法,找到大于等于n,小于等于m的素数
for(int i=0; i<maxn; i++)
    is[i]=1;
int d=sqrt(m+0.5);
for (LL i = 0; i < cnt && p[i]<= d; i++)
{
 
    int s = n/ p[i] + (n% p[i] > 0);
    if (s == 1) s = 2;
    for (LL j = s; j*p[i] <= m; j++)
        if (j*p[i] >= n)
            is[j*p[i]-n] = 0;
}