根本不会,先copy下来,未来再看
#include <bits/stdc++.h>
using namespace std;
const int N = 45000;
int s;
int primes[N], cnt;
bool vis[N];
int ans[N], sz;
void get_prime(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
vis[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
bool is_prime(int x) {
if (x < N) return !vis[x];
for (int i = 0; primes[i] <= x / primes[i]; i++) {
if (x % primes[i] == 0) return false;
}
return true;
}
void dfs(int cur, int prod, int num) {
if (prod == s) { // 搜索得到的质数和prod等于s
ans[sz++] = num;
return;
}
int r = s / prod; // 要凑的剩余部分
if (is_prime(r - 1) && (r - 1) >= primes[cur]) ans[sz++] = num * (r - 1); // 先考虑质因子大于sqrt(r)的情况
for (int i = cur; primes[i] <= r / primes[i]; i++) { // 再考虑质因子小于sqrt(r)的情况
for (int j = 1 + primes[i], k = primes[i]; j <= r; k *= primes[i], j += k) { // 枚举质数i对应的次幂
if (r % j == 0) dfs(i + 1, prod * j, num * k);
}
}
}
int main() {
get_prime(N - 1); // 筛出不超过sqrt(2e9)的质数
while (~scanf("%d", &s)) {
sz = 0;
dfs(0, 1, 1); // 从第0个质数开始枚举搜索
printf("%d\n", sz);
if (sz) {
sort(ans, ans + sz);
for (int i = 0; i < sz; i++) {
printf("%d ", ans[i]);
}
printf("\n");
}
}
return 0;
}