【线性筛】漂亮数

今天药忘吃喽~ 2024-03-24 08:08 3阅读 0赞

[1006-漂亮数\_2021秋季算法入门班第十章习题：数学 (nowcoder.com)][1006-_2021_ _nowcoder.com]

题意：

![28c4c18701aaa235ee5e793f17f35b59.png][]

思路：

首先肯定是前缀和预处理出前缀有几个漂亮数

然后问题就是怎么快速判断一个数是否为漂亮数：由两个质数的乘积组成

所以可以去考虑线性筛的过程，当一个质数作为最小质因子去筛别的数的时候，且i也是质数的时候i\*prime\[j\]就是两个质数的乘积，此时就可以标记漂亮数了

**当涉及到最小质因子的时候，用线性筛是最合适不过的了**

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    using i64 = long long;
    const int mxn=1e8+10;
    const int mxe=1e8+10;
    const int mod=1e9+7;
    int len=0,l,r;
    bool vis[mxn],st[mxn];
    int prime[mxn],sum[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(!vis[i]) st[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
        for(int i=1;i<=1e8;i++) sum[i]=sum[i-1]+st[i];
    }
    void solve(){
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        p_init(1e8);
        while(__--)solve();return 0;
    }

[1006-_2021_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/26656/1006
[28c4c18701aaa235ee5e793f17f35b59.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/91e92e71283d4107a142ee202d5d99f1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关【线性筛】阶乘约数

看老师写的DP看了一万年终于有点会了题意： ![597c1378397f2be58a7114e70521a2f6.png][] 思路：先去跑线性筛，把一个数的最

你的名字/ 2024年03月26日 18:30/ 0 赞/ 62 阅读

相关【线性筛+DP】最大和

看错题了，呃呃，其实就是个简单DP [最大和 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题意： ![1c1959b04b63553193

系统管理员/ 2024年03月26日 16:51/ 0 赞/ 62 阅读

相关【线性筛】漂亮数

[1006-漂亮数\_2021秋季算法入门班第十章习题：数学 (nowcoder.com)][1006-_2021_ _nowcoder.com] 题意： ![28c4c1

今天药忘吃喽~/ 2024年03月24日 08:08/ 0 赞/ 4 阅读

相关质数 AcWing 868. 筛质数线性筛

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

水深无声/ 2023年09月28日 11:35/ 0 赞/ 7 阅读

相关 P3383 【模板】线性筛素数---洛谷

题目描述题目背景本题已更新，从判断素数改为了查询第 k 小的素数提示：如果你使用 cin 来读入，建议使用 std::ios::sync\_with\_st

雨点打透心脏的1/2处/ 2023年07月18日 06:54/ 0 赞/ 9 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 145 阅读

相关 Problem 50 Consecutive prime sum （线性筛）

Consecutive prime sum Problem 50 The prime 41, can be written as the sum of six co

深藏阁楼爱情的钟/ 2022年07月15日 03:22/ 0 赞/ 154 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 268 阅读

相关素数线性筛模板

[参考于该博客][Link 1] int Mark[MAXSIZE]; int prime[MAXSIZE]; //判断是

╰+哭是因爲堅強的太久メ/ 2022年05月14日 03:36/ 0 赞/ 239 阅读

相关 [模板] 积性函数 && 线性筛

积性函数数论函数指的是定义在正整数集上的实或复函数. 积性函数指的是当 \\((a,b)=1\\) 时, 满足 \\(f(a\b)=f(a)\f(b)\\) 的数论

左手的ㄟ右手/ 2022年01月08日 00:43/ 0 赞/ 217 阅读