模运算，质因数分解
链接：https://ac.nowcoder.com/acm/contest/9982/I
来源：牛客网

算数基本定理，又称唯一分解定理，算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。
朴素的质因子分解算法就是利用了算数基本定理，依次枚举p判断N是否包含素因子p。牛牛最近对于质因数分解产生了浓厚的兴趣。牛牛定义了一个函数F(x)，它表示将x做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。

例如 1500=2*2*3*5*5*5,F(1500)=223555。

牛牛现在想要知道发f[2]+f[3]...+f[n]的值。
由于这个结果非常大，所以你只用告诉牛牛最终答案对10^9 +7取余数的结果即可。
输入描述:
仅一行一个正整数 n (2~ 4e6)
输出描述:
仅一行，表示答案对10^9+7 取余数的结果。
输入
10
输出
342
思路：
需要提前处理，注意n比较大

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e6+10;
const int mod = 1e9+7;
ll a[N],f[N],ff[N],b[22],c[22];
ll ii = 0;ll tex = 0;
bool t[N];

void f1()//素数筛
    for(int i = 2; i < N;i++){
        int j = i;
        if(!t[i]){
            a[ii] = i;f[i] = i;ff[i] = 1;
            ii++;
            while(j < N){
                t[j] = 1;
                j += a[ii-1];
            }
        }
    }
}
void f2(){//递推寻找到前 n 的质因数分解情况
    for(ll i = 2;i < n+10;i++){
        if(ff[i]) continue;
        ll j = i;
        ll k = 0;
        while(j!=1){
            while(j%a[k]==0){
                ff[i] = a[k];
                j = 1;
            }
            k++;
        }
    }
}
void inf(ll k,ll num){//将每个质因子按要求链接起来，并取模
    f[k] = b[0];
    for(int i = 1; i < num; i++){
        int t = b[i];
        int j = 0;
        int t1;
        while(t){
            t1=t%10;t/=10; c[j] = t1;j++;
        }
        if(j)
        for(int l = j-1; l>=0;l--){
            f[k]*=10;
            f[k]+=c[l];
            f[k]%=mod;
        }
    }
}
void f3(int n){
    for(ll i = 2;i<n;i++){
        if(f[i]) continue;
        ll j = i;
        ll num = 0;
        memset(b,0,sizeof(b));
        for(;ff[j]!=1;){//将i的质因子存入 数组b 中
            b[num] = ff[j];
            num++;
            j/=ff[j];
        }
        b[num] = j;
        num++;
        inf(i,num);
    }
}
int  main(){
    int n;
    cin >> n;
    f[2] = 2,f[3] =3,f[4] = 22,f[5] = 5,f[6] = 23;
    ff[0] =1,ff[1] =1;
    f1();
    f2();
    f3(n);

    ll sum = 0;
    for(int i = 2; i <= n; i++){
        sum += f[i];
        sum %= mod;
    }
    cout << sum;
    return  0;
}

附：基本模运算
图片说明