频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
数论 - 线性筛法与积性函数
2015-08-10 08:58:48         来源:Never say never  
收藏   我要投稿

首先以求1000000以内的素数为例来探讨筛法

Eratosthenes筛法(埃拉托斯特尼筛法)

时间复杂度:O(N*loglogN)
空间复杂度:O(N)

代码:

#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 1000005;

bool vis[maxn];
int prime[maxn];
int tot;

void init() {
    tot = 0;
    memset(vis, false, sizeof(vis));
    for(int i = 2; i < maxn; i ++) {
        if(!vis[i]) {
            prime[tot ++] = i;
            for(int j = i * 2; j < maxn; j += i) {
                vis[j] = true;
            }
        }
    }
}

int main() {

    init();

    for(int i = 0; i < 100; i ++) {
        cout << prime[i] <<  ;
    }

    return 0;
}

 


Euler筛法(欧拉筛法)

每个合数只会被它最小的质因数筛去,因此时间复杂度为O(N)。

此种为线性筛法

代码:

#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 1000005;

bool vis[maxn];
int prime[maxn];
int tot;

void init() {
    tot = 0;
    memset(vis, false, sizeof(vis));
    for(int i = 2; i < maxn; i ++) {
        if(!vis[i]) prime[tot ++] = i;
        for(int j = 0; j < tot; j ++) {
            if(i * prime[j] > maxn) break;
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main() {

    init();

    for(int i = 0; i < 100; i ++) {
        cout << prime[i] <<  ;
    }

    return 0;
}

 


线性筛法求欧拉函数

代码:

#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 1000005;

bool vis[maxn];
int prime[maxn];
int fai[maxn];
int tot;

void init() {
    memset(vis, false, sizeof(vis));
    fai[1] = 1;
    tot = 0;
    for(int i = 2; i < maxn; i ++) {
        if(!vis[i]) {
            prime[tot ++] = i;
            fai[i] = i - 1;
        }
        for(int j = 0; j < tot; j ++) {
            if(i * prime[j] >= maxn) break;
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                fai[i * prime[j]] = fai[i] * prime[j];
                break;
            }
            else {
                fai[i * prime[j]] = fai[i] * (prime[j] - 1);
            }
        }
    }
}

int main() {

    init();

    for(int i = 1; i < 100; i ++) {
        cout << fai[i] <<  ;
    }

    return 0;
}

 


线性筛法求莫比乌斯函数

代码:

#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define INF 0x7fffffff
using namespace std;

const int maxn = 1000005;

bool vis[maxn];
int prime[maxn];
int mu[maxn];//莫比乌斯函数
int tot;

void init() {
    memset(vis, false, sizeof(vis));
    mu[1] = 1;
    tot = 0;
    for(int i = 2; i < maxn; i ++) {
        if(!vis[i]) {
            prime[tot ++] = i;
            mu[i] = -1;
        }
        for(int j = 0; j < tot; j ++) {
            if(i * prime[j] >= maxn) break;
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            else {
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
}

int main() {

    init();

    for(int i = 1; i < 100; i ++) {
        cout << mu[i] <<  ;
    }

    return 0;
}

 

 载。

点击复制链接 与好友分享!回本站首页
相关TAG标签 数论 线性 函数
上一篇:_DataStructure_C_Impl:Array
下一篇:Chromium多进程架构简要介绍和学习计划
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站