65 lines
1.8 KiB
C++
65 lines
1.8 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int INF = 0x3f3f3f3f;
|
||
|
||
typedef long long LL;
|
||
LL l = 1, r = 2000000;
|
||
|
||
const int N = 1e7 + 10;
|
||
//欧拉筛[线性筛法]
|
||
int primes[N], cnt; // primes[]存储所有素数
|
||
bool st[N]; // st[x]存储x是否被筛掉
|
||
void get_primes(int n) {
|
||
for (int i = 2; i <= n; i++) {
|
||
if (!st[i]) primes[cnt++] = i;
|
||
for (int j = 0; primes[j] <= n / i; j++) {
|
||
st[primes[j] * i] = true;
|
||
if (i % primes[j] == 0) break;
|
||
}
|
||
}
|
||
}
|
||
|
||
vector<int> v[N];
|
||
|
||
int main() {
|
||
/**=====================================================***/
|
||
//计时开始
|
||
clock_t startTime= clock();
|
||
/**=====================================================***/
|
||
|
||
//1、筛出小于sqrt(r)的所有质数
|
||
get_primes(sqrt(r));
|
||
|
||
//2、遍历每个数字，求质因子
|
||
for (LL i = l; i <= r; i++) {
|
||
int t = i;
|
||
for (int j = 0; j < cnt && primes[j] * primes[j] <= i; j++) {
|
||
if (i % primes[j] == 0) {
|
||
v[i].push_back(primes[j]);
|
||
//除干净这个质数因子
|
||
while (t % primes[j] == 0) t /= primes[j];
|
||
}
|
||
}
|
||
if (t > 1) v[i].push_back(t);
|
||
}
|
||
|
||
//输出质数因子有哪些
|
||
for (int i = l; i <= r; i++) {
|
||
cout << i << ": ";
|
||
for (auto c:v[i]) cout << c << " ";
|
||
cout << endl;
|
||
}
|
||
cout << endl;
|
||
|
||
/**************************************************************/
|
||
//计时结束
|
||
clock_t endTime = clock();
|
||
cout << "The run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
|
||
/**=====================================================***/
|
||
//The run time is: 4.273s
|
||
return 0;
|
||
}
|
||
|
||
|