微网站开发服务,wordpress 安全性设置,兰州网站制作公司排名,连锁销售网站制作这道题目比较经典#xff0c;或者说这种思想比较经典。 这种筛法的思想。 我们正着想对于每一个 n 、 n − 1 、 n − 2 、 . . . 、 2 、 1 n、 n-1、n-2、...、2、1 n、n−1、n−2、...、2、1都分解一遍质因数显然是来不及的时间复杂度达到 O ( n n ) O(n \sqrt{n}) O(nn … 这道题目比较经典或者说这种思想比较经典。 这种筛法的思想。 我们正着想对于每一个 n 、 n − 1 、 n − 2 、 . . . 、 2 、 1 n、 n-1、n-2、...、2、1 n、n−1、n−2、...、2、1都分解一遍质因数显然是来不及的时间复杂度达到 O ( n n ) O(n \sqrt{n}) O(nn ) 我们考虑对于每一个1e6以内的质因数的个数 跑了一下程序是 78498 78498 78498个 素数定理告诉我们不超过x的素数近似有 x l n x \frac{x}{lnx} lnxx个 对于每一个质因子我们看一下那些数有一个这个质因子那些数有两个那些数有3个这个每次是平方的增长很快 时间复杂度: O ( n l o g x ∗ l o g n ) O(\frac{n}{logx} * logn) O(logxn∗logn)近似 O ( n ) O(n) O(n)
#include bits/stdc.h
#define int long long
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define pii pairint, int
#define pll pairlong long, long long
#define ll long long
#define db double
#define endl \n
#define x first
#define y second
#define pb push_backusing namespace std;const int N1e610,mod1e97;
int vis[N];
vectorintp;
void solve()
{int n;cinn;auto get[](int x){rep(i,2,x){if(!vis[i]) p.pb(i);for(int j0;p[j]*ix;j){vis[i*p[j]]1;if(i%p[j]0) break;}}};get(1e6);coutp.size()endl;int res0;vectorintans(n1);rep(i,0,p.size()-1){for(int jp[i];jn;j*p[i]){ans[i]n/j;resn/j;}}rep(i,0,p.size()-1){coutp[i] ans[i]endl;}return;
}signed main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen(1.in, r, stdin);int _;
// cin_;
// while(_--)solve();return 0;
}
