牛客算法入门数学：1001-1006 质数

0x00 题目来源

数学专题

0x10 Tag

数学、素数、欧拉筛

---

0x20 1001-素数判断

给出一个数x，判断它是否为素数，并输出所有它的素因子。

0x21 素数筛(欧拉筛)

板子如下:

bool isnp[MAXN];
vector primes;
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}

埃氏筛一种朴素地筛选素数的方法，从小到大利用质数筛选合数。但问题是，和数会被两个以上质数筛去，例如：30会被2，3，5重复筛去。

所以我们引入欧拉筛，以下我们模拟以下筛取的过程

假设数组 A = [ 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 ] A=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] A=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]此时质数表 P = [ ] P=[] P=[];

第一次遍历A,将第一个未被筛的数放入质数表 P = [ 2 ] P=[2] P=[2];
并选定2，将2与质数表所有数相乘(只有2)，筛去相乘结果(4)
数组 A = [ 2 , 3 , 4 ∗ , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 ] A=[2,3,4* ,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] A=[2,3,4∗,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
数字后面的*表示已经被筛去

第二次遍历A,将第一个未被筛的数放入质数表 P = [ 2 , 3 ] P=[2,3] P=[2,3];
并选定3，将3与质数表所有数相乘(2,3)，筛去相乘结果(6,9)
数组 A = [ 2 , 3 , 4 ∗ , 5 , 6 ∗ , 7 , 8 , 9 ∗ , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 ] A=[2,3,4* ,5,6*,7,8,9*,10,11,12,13,14,15,16,17,18,19,20] A=[2,3,4∗,5,6∗,7,8,9∗,10,11,12,13,14,15,16,17,18,19,20]

第三次遍历A,发现4已经被筛去
选定4，将4与质数表所有数相乘(2,3)，筛去相乘结果(8,12)？？

欧拉筛最重要的不同点在这里，如果我们遍历质数表取 p p p发现 p p p整除我们选定的数字，应该停止筛去，因为欧拉筛的核心是用最小的质因数筛去合数。在这个例子中，12应该被2筛去(在 2 × 6 2times 6 2×6中被筛去)，所以我们只划去8， A = [ 2 , 3 , 4 ∗ , 5 , 6 ∗ , 7 , 8 ∗ , 9 ∗ , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 ] A=[2,3,4* ,5,6*,7,8*,9*,10,11,12,13,14,15,16,17,18,19,20] A=[2,3,4∗,5,6∗,7,8∗,9∗,10,11,12,13,14,15,16,17,18,19,20]。if (i % p == 0) break;模拟的就是中止筛去的过程

第四次遍历A,将第一个未被筛的数放入质数表 P = [ 2 , 3 , 5 ] P=[2,3,5] P=[2,3,5];
选定5，将5与质数表所有数相乘(2,3)，筛去相乘结果(10,15,25)
数组 A = [ 2 , 3 , 4 ∗ , 5 , 6 ∗ , 7 , 8 , 9 ∗ , 10 ∗ , 11 , 12 , 13 , 14 , 15 ∗ , 16 , 17 , 18 , 19 , 20 ] A=[2,3,4* ,5,6*,7,8,9*,10*,11,12,13,14,15*,16,17,18,19,20] A=[2,3,4∗,5,6∗,7,8,9∗,10∗,11,12,13,14,15∗,16,17,18,19,20]
…

0x22 O(sqrt(n)) 判断素数

bool isP(long long n){
    if(n == 1) return 0;
    if(n == 2) return 1;
    if(!(n&1)) return 0;
    for(long long i = 3;i*i<=n;i+=2) if(!(n%i)) return 0;
    return 1;
}

0x22 O(logN) 分解质因数

vector n_primes;
void dec(int n)
{
    n_primes.clear();
    while(n%2==0)
    {
        n_primes.push_back(2);
        n/=2;
    }
    for(int i=3;i<=sqrt(n*1.0);i+=2)
    {
        while(n%i==0)
        {
            n_primes.push_back(i);
            n/=i;
        }
    }
    if(n>2)
        n_primes.push_back(n);
}

具体流程为

除以所有以 2 为倍数的因子枚举以 i 为倍数为因子的整数防止 n 本身是个素数

第一步将复杂度优化到O(logN)

0x23 set去重

	vectorv;
	sets(v.begin(),v.end());
    v.assign(s.begin(),s.end());

---

0x20 1002-素数判断

现在给出一个素数，这个素数满足两点：
1、 只由1-9组成，并且每个数只出现一次，如13,23,1289。
2、 位数从高到低为递减或递增，如2459，87631。
请你判断一下，这个素数的回文数是否为素数（13的回文数是131,127的回文数是12721）。

模拟构造回文串，判断isP()即可

这题见鬼了

for(ll i=2;i*i<=x;i++)

不写成long long会超时而不是Wa

---

0x40 1004-素数分布

素数分布函数pi (n)π(n)表示小于或等于n的素数的数目。例如pi (10)=4π(10)=4（2,3,5,7是素数）。这个函数涉及到许多高等数论的内容，甚至和黎曼猜想挂钩，目前还有很多数学家正在不断探索其中的奥秘。千里之行始于足下，现在你开始关心一个问题：在正整数域中素数的分布是怎么样的。为了探索这个问题，你需要计算出一些pi (n)π(n)的值。

素数筛模板即可

---

0x50 1005-Forsaken喜欢数论

Forsaken有一个有趣的数论函数。对于任意一个数x，f(x)会返回x的最小质因子。如果这个数没有最小质因子，那么就返回0。
现在给定任意一个n，Forsaken想知道 ∑ i = 1 n sum_{i = 1}^{n} ∑i=1n​的值。

数据范围 1≤n≤3e7

最开始我有两种想法：一种是打表后，对于每一个x遍历整个质数表寻找它的最小质因子(第一个可整除的质数)，但它的时间复杂度接近 O ( n 2 + n ) O(n^2+n) O(n2+n)。另一种打表后,每个数分解质因数，找到最小的质因数，复杂度为 O ( n l o g n + n ) O(nlogn+n) O(nlogn+n) 。均会被 3 e 7 3e7 3e7卡死。

正确做法应该为，打表时记录最小质因子，如下代码：

void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
        {
            primes.push_back(i),ans+=i;
        }
            
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            ans+=p;
            if (i % p == 0)
                break;
        }
    }
}

原因是欧拉筛是用最小的质因数筛去合数。时间复杂度为 O ( n ) O(n) O(n)，满足题设。

---

0x60 1006-漂亮数

小红定义一个数满足以下条件为“漂亮数”：

该数不是素数。该数可以分解为2个素数的乘积输入 l 和 r ，请你输出 [l,r] 闭区间中有多少个漂亮数。

第一行输入一个正整数 t ，代表有 t 次询问
两个正整数 l 和 rr ，用空格隔开。
1 ≤ t ≤ 1 0 5 1 leq t leq 10^5 1≤t≤105
1 ≤ l , r ≤ 1 0 8 1le l,rle 10^8 1≤l,r≤108

打表后再分解因数时间复杂度 O ( T ( n + n l o g n ) ) O(T(n+nlogn)) O(T(n+nlogn)),显然超时(虽然给定了3s)
这题的正解应该为分别打表确定漂亮数，而询问区间数量可以通过前缀和的方式将复杂度降低到 O ( 1 ) O(1) O(1),总复杂度 O ( T ( n ) ) O(T(n)) O(T(n))。

代码如下:

#include 
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 0x7fffffff;
#define f(i,a,b) for(int i = a;i < b;i++)
#define fd(i,a,b) for(int i = a;i > b;i--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ret return
#define HACK freopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#define RT double rtime = 1.0 * clock() / CLOCKS_PER_SEC;cout<<"nRuntime: "<void write(T x)
    {
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }

    template void read(T &x)
    {
        x = 0;char ch = getchar();int f = 1;
        while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
        while(isdigit(ch)){x = x*10+(ch-'0');ch=getchar();}x*=f;
    }
};
using namespace IO;
const int MAXN=1e8+10;
int bt[MAXN];
bool isnp[MAXN];
vector primes;
void init1(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
                break;
        }
    }
}
void init2(int n)
{
    for(auto x:primes)
    {
        for(auto y:primes)
        {
            if(y>x) break;
            if(x*y>n) break;
            bt[x*y]=1;
        }
    }
    
}
int main()
{
    #ifdef LOCAL_JUDGE
    HACK;
    #endif

    init1(MAXN);
    init2(MAXN);
    partial_sum(bt, bt + MAXN, bt);
    int t;
    read(t);
    while(t--)
    {
        int l,r;
        read(l);
        read(r);
        cout< 
0x61 优化 
以上代码仍旧会超时=_=,原因有两点：一个是自带的前缀和partial_sum()常数比较大，效率低，需要手敲；另外两个数相乘得到另一个数，一定有
    
     
      
       
        x
       
       
        ≤
       
       
        y
       
      
      
       xle y
      
     
    x≤y,在打表漂亮数时，的二层循环可以从
    
     
      
       
        i
       
      
      
       i
      
     
    i开始。
 
void init2(int n)
{
    f(i,1,primes.size()+1)
    {
        f(j,i,primes.size()+1)
        {
            if(primes[i]*primes[j]>MAXN) break;
            bt[primes[i]*primes[j]]=1;
        }
    }
    
}
 
0x70 另 
 
 
=)