x*****0
发帖数: 452 | 1 给定一个range(int a, int b)，找到这个range里面的good number， good number的
定义是：所有组成它的prime factor的个数也是个prime number。
例子：
input: range [1 10]
good number: 6, 10
一个很直观的解法就是对数组中的树一个个去做prime factorization, 然后count。
请问有更加高效的解法吗？ | b********0
发帖数: 62 | 2 在筛选法之上再加一点 感觉可以做
【在 x*****0 的大作中提到】
: 给定一个range(int a, int b)，找到这个range里面的good number， good number的
: 定义是：所有组成它的prime factor的个数也是个prime number。
: 例子：
: input: range [1 10]
: good number: 6, 10
: 一个很直观的解法就是对数组中的树一个个去做prime factorization, 然后count。
: 请问有更加高效的解法吗？
| x*****0
发帖数: 452 | 3 请问可以稍稍说的再详细一点吗？
【在 b********0 的大作中提到】
: 在筛选法之上再加一点 感觉可以做
| i********y
发帖数: 34 | 4 class Solution {
vector counts;
public:
int getPrimeCount(int n, int k) {
while (1) {
// make sure k is prime
while (k < n && counts[k] != 1) ++k;
if (n%k == 0) {
while (n%k == 0) n /= k;
return counts[n] + 1;
}
++k;
}
}
vector solve(int n) {
counts.resize(n + 1);
vector ret;
for (int i = 2; i <= n; ++i) {
int count = getPrimeCount(i, 2);
counts[i] = count;
if (counts[count] == 1) ret.push_back(i);
}
return ret;
}
};
【在 x*****0 的大作中提到】
: 给定一个range(int a, int b)，找到这个range里面的good number， good number的
: 定义是：所有组成它的prime factor的个数也是个prime number。
: 例子：
: input: range [1 10]
: good number: 6, 10
: 一个很直观的解法就是对数组中的树一个个去做prime factorization, 然后count。
: 请问有更加高效的解法吗？
|
|
