第二次课-唯一分解定理+埃氏筛

snowane · 2025-07-26 21:31:23 · 个人记录

唯一分解定理(分解质因数)

模板(函数)：

void calc(int n)
{
    for(int i=2;i<=n/i;i++)
    {
        while(n%i==0)
        {
            cout<<i<<" ";//注：此处输出格式因题而异
            n/=i;
        }
    }
    if(n>1)
    {
        cout<<n;
    }
}

原理

1.第一重循环：最小的质数为2，所以从2开始试，由于因子是一对一对地出现，所以试到n/i就行了

2.while循环：要一直模到不能再模才能把后面此质数的倍数都删掉。顺路提一嘴，凡是能进入while循环都是质数，因为如果不是，早已在前面删掉了

3.除法：当n将i给除掉时，已经将其倍数都去掉了

4.if判断：如果n是质数，就会在此输出，因为它一直没被除掉

埃氏筛(找到所有质数)

运行次数：log(2)=1

      log(4)=2
      log(8)=3
      log(16)=4
      ·
      ·
      ·

1/1+1/2+1/3+...+1/n =log(n)

模板（函数）：

bool cz[105];
int sz[105];
int cnt=0;
void getprimes(int n)
{
    cz[0]=1;
    cz[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(cz[i]==0)
        {
            for(int i=2*i;i<=n;i+=i)
            {
                cz[i]=1;
            }
            sz[++cnt]=i;
        }
    }
}

原理

1.将第一项与第二项变为1：0和1既不是质数，也不是合数，所以为1

2.if判断：为0时说明为质数

3.第二重for循环：是i的倍数的数必为合数，所以都为1

4.将i存入sz数组： 这行代码与 cnt++； sz[cnt]=i; 相同