题目
最大素因数
$13195$ 的素因数是 $5,7,13$ 和 $29$。
那么 $600851475143$ 的最大素因数是多少？
Largest Prime Factor
The prime factors of $13195$ are $5,7,13$ and $29$ .
What is the largest prime factor of the number $600851475143$ ?
解题方法
试除法
已知正整数 $n=600851475143$ ,则 $n$ 的素因数必然为小于等于 $\sqrt{n}$ 的素数。
因此，可以使用「埃氏筛法」或者「欧拉筛法」筛选出小于 $\sqrt{n}$ 的素数，并在筛选时判断是否为 $n$ 的素因数。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <format>
std::uint64_t prime_factor(std::uint64_t num) {
const std::uint64_t sqrt {
static_cast<std::uint64_t>(std::floor(std::sqrt(num)))
};
std::vector<std::uint64_t> result;
std::vector<std::uint64_t> prime(sqrt + 1, 0);
std::vector<std::uint64_t> visit(sqrt + 1, 0);
for (std::uint64_t i = 2; i <= sqrt; ++i) {
if (!visit[i]) {
prime[++prime[0]] = i;
while (num % i == 0) { // 进行判断
num /= i;
result.push_back(i);
if (num == 1) {
return *result.rbegin();
}
}
}
for (std::uint64_t j = 1; j <= prime[0] && i * prime[j] <= sqrt; ++j) {
visit[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
return UINT64_MAX;
}
int main() {
constexpr std::uint64_t N{ 600851475143ll }; // sqrt(N) = 775146.0992245268
std::cout << std::format("Project Euler 3 result: {}\n", prime_factor(N));
}
|
参考链接
