`
huyifan951124
  • 浏览: 82897 次
社区版块
存档分类
最新评论

hdu5901 Meisell-Lehmer算法求素数个数

 
阅读更多

题目大意:让你求1-n里面有几个素数(1<=n&&n<=1e11)。

算法思路:这里的n非常大,因此我们用Meisell-Lehmer算法求1-n的个数,该算法的复杂度为n^(2/3)

#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
const int N = 5e6 + 2;
bool np[N];
int prime[N], pi[N];
int getprime()
{
    int cnt = 0;
    np[0] = np[1] = true;
    pi[0] = pi[1] = 0;
    for(int i = 2; i < N; ++i)
    {
        if(!np[i]) prime[++cnt] = i;
        pi[i] = cnt;
        for(int j = 1; j <= cnt && i * prime[j] < N; ++j)
        {
            np[i * prime[j]] = true;
            if(i % prime[j] == 0)   break;
        }
    }
    return cnt;
}
const int M = 7;
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;
int phi[PM + 1][M + 1], sz[M + 1];
void init()
{
    getprime();
    sz[0] = 1;
    for(int i = 0; i <= PM; ++i)  phi[i][0] = i;
    for(int i = 1; i <= M; ++i)
    {
        sz[i] = prime[i] * sz[i - 1];
        for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1];
    }
}
int sqrt2(LL x)
{
    LL r = (LL)sqrt(x - 0.1);
    while(r * r <= x)   ++r;
    return int(r - 1);
}
int sqrt3(LL x)
{
    LL r = (LL)cbrt(x - 0.1);
    while(r * r * r <= x)   ++r;
    return int(r - 1);
}
LL getphi(LL x, int s)
{
    if(s == 0)  return x;
    if(s <= M)  return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
    if(x <= prime[s]*prime[s])   return pi[x] - s + 1;
    if(x <= prime[s]*prime[s]*prime[s] && x < N)
    {
        int s2x = pi[sqrt2(x)];
        LL ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
        for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]];
        return ans;
    }
    return getphi(x, s - 1) - getphi(x / prime[s], s - 1);
}
LL getpi(LL x)
{
    if(x < N)   return pi[x];
    LL ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1;
    for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1;
    return ans;
}
LL lehmer_pi(LL x)
{
    if(x < N)   return pi[x];
    int a = (int)lehmer_pi(sqrt2(sqrt2(x)));
    int b = (int)lehmer_pi(sqrt2(x));
    int c = (int)lehmer_pi(sqrt3(x));
    LL sum = getphi(x, a) +(LL)(b + a - 2) * (b - a + 1) / 2;
    for (int i = a + 1; i <= b; i++)
    {
        LL w = x / prime[i];
        sum -= lehmer_pi(w);
        if (i > c) continue;
        LL lim = lehmer_pi(sqrt2(w));
        for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1);
    }
    return sum;
}
LL n;
int main()
{
    init();
    while(scanf("%lld",&n)!=EOF)
    {
        printf("%lld\n",lehmer_pi(n));
    }
    return 0;
}

 

0
0
分享到:
评论

相关推荐

    HDU-2000-2099.zip_hdu2000

    【标题】"HDU-2000-2099.zip_hdu2000" 是一个包含杭电(Hangzhou Dianzi University)ACM竞赛题目解题报告的压缩包,覆盖了编号从2000到2099的题目。这个资源对于学习算法、提高编程技巧以及准备ACM/ICPC(国际大学...

    HDU+2000-2099+解题报告

    这个压缩包文件“HDU 2000-2099 解题报告”显然包含了在这个题号范围内的一些问题、答案以及解题思路,对于学习算法和提升编程能力具有很高的价值。 在这个范围内,我们可以预见到涵盖的算法类型可能包括但不限于:...

    HDU-EID-V2-核心板1

    在本话题中,我们关注的是一个名为"HDU-EID-V2-核心板1"的特定设计,它涉及到STM32的核心组件、接口、电源管理和调试配置。 首先,核心板设计中提到了F103和F207两个型号的STM32芯片。F103和F207属于STM32的不同...

    HDU-1535-.zip_多源点

    描述中提到的"求多源点到单终点的最短路(反向建图)"进一步说明了问题的核心是找到从多个起点到一个固定终点的最短路径,并且采用了“反向建图”的策略。 在图论中,最短路径问题是一个经典问题,通常我们使用 ...

    2019-hdu-multi-(2019杭电多校第二场数据与标程).zip

    总结来说,《2019-hdu-multi-(2019杭电多校第二场数据与标程).zip》是一个宝贵的编程竞赛学习材料,它涵盖了算法设计、编程实践、数据分析以及团队合作等多个方面,对于提高编程能力和参与类似竞赛的准备都非常有...

    HDU+2000-2099+解题报告.zip

    《杭电OnlineJudge 2000-2099解题报告》是针对杭州电子科技大学(HDU)在线评测系统(OnlineJudge)中2000至2099题目的详细解答集锦,主要涵盖了算法分析、编程技巧以及问题解决策略等内容。这份解题报告以CHM...

    HDU-2000-2099.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个知名的编程竞赛平台,为编程爱好者提供了大量的算法题目进行练习和比赛。这个名为"HDU-2000-2099.rar_hdu"的压缩包包含了该平台从2000到2099共100道题目的源代码。这些...

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo.zip

    hdu-OS-simple-shell,Linux_的_Shell_命令窗口_demo_版实现_shell-demo

    算法-数塔(HDU-2084).rar

    总的来说,这个数塔问题提供了锻炼和提高编程技巧的机会,特别是对于那些对算法和数据结构感兴趣的开发者。通过解决这样的问题,不仅可以提升解决问题的能力,还能增强对计算机科学基础的理解。

    HDU-EID-V2-扩展板1

    HDU-EID-V2-扩展板1是一款专为STM32微控制器设计的硬件扩展板,主要用于增强核心板的功能。该扩展板具有多种接口和功能,包括ADC(模数转换器)、电位器、DAC(数模转换器)输出以及TEST_V跳线,能够满足用户在模拟...

    hdu ACM代码 每种算法都有分类

    HDU ACM代码集合是针对ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)的一份资源,这个压缩包中的代码涵盖了多种算法,是参赛者或对算法学习感兴趣的人宝贵的参考资料。ACM竞赛旨在...

    hdu-page-11-answer.rar_hdu_hdu oj第十一页_page_搜题_杭电oj

    总之,"HDU Page 11 Answer"是ACM初学者和杭电OJ用户的宝贵参考资料,它涵盖了基础算法的实践应用,能帮助学习者快速提升编程能力和算法思维。通过系统学习和不断练习,你将逐渐精通各类算法,为未来的编程之路打下...

    ACM HDU 2000-2099 解题报告 杭电 ACM

    《ACM HDU 2000-2099 解题报告 杭电 ACM》是一份详尽的编程竞赛解题集,主要涵盖了杭电(Hangzhou Dianzi University)在线判题系统(HDU OJ)上的2000至2099号题目。这份解题报告是针对参与ACM/ICPC(国际大学生...

    HDU-Coder-X#Daily-question-of-Leetcode#2022-04-04-307. 区域和检索 - 数

    其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和

    ACM-HDU涉及了很多算法

    在ACM(国际大学生程序设计竞赛)中,HDU(杭州电子科技大学)的在线判题系统是许多参赛者磨炼算法技巧的重要平台。这个平台涵盖了众多的算法问题,旨在提升参赛者的编程能力和逻辑思维能力。以下是对标题和描述中...

    HDU-Coder-X#Daily-question-of-Leetcode#2022-02-26-2016. 增量元素之间的最

    2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]

    HDU算法讲解的PPT

    HDU算法讲解的PPT是一份非常有价值的教育资源,由知名教育机构HDU(杭州电子科技大学)的lcy老师精心制作并讲解。这份PPT涵盖了算法的各个方面,是学习和提升算法能力的理想材料。标签“算法”、“讲解”和“经典”...

Global site tag (gtag.js) - Google Analytics