我试图找到数字 600851475143 的最大质因数。我的代码适用于我测试的较小数字（低于 100）。然而，当遇到 600851475143 时，它返回 4370432，绝对不是质数。有什么想法我的代码可能有什么问题吗？
#include <iostream>
#include <time.h>
#include <math.h>
using namespace std;
int main()
{
int num;
int largest;
int count;
cout<<"Please enter a number to have its Largest Prime Factor found"<<endl;
cin>>num;
num = 600851475143;
for (int factor = 1; factor <= num; factor++)
{
if (num % factor == 0)
{
count = 0;
for (int primetest=2; count == 0 && factor > primetest ; primetest++)
{
if (factor % primetest == 0)
count ++;
//endif
}
if (count == 0)
largest = factor;
//endif
}
}//endif
cout<<largest<<endl;
system("PAUSE");
}
num = 600851475143;
这里出现整数溢出。
num使用
uint64_t#include <cstdint> //must include this!
uint64_t num = 600851475143;
读这个：cstdint
代码有不少大问题，所以我想展示一个更好的完整 解决方案。主要问题是它没有输入验证！好的代码一定是正确的 它不会拒绝所有输入。所以我现在已经包括了正确的阅读和验证 输入。这样你就会自动发现问题。
所有主要类型都需要有专有名称！所以我介绍了 typedef uint_type。 如果输入 60085147514 是 有效与否（尽管这在运行时也被拒绝）。如果编译器警告， 那么你需要使用更大的整数类型；然而 unsigned long 在所有常见的情况下就足够了 64 位平台（但不在常见的 32 位平台上）。如果您需要更大的整数类型， 那么现在只需要更改一个地方。
你的算法效率低得可怕！所需要的只是将数字除以 找到所有因子（尽可能长），保证你只会遇到质数 数字 - 因此无需检查。而且一个人只需要考虑以下因素 输入的平方根。这一切都需要一些逻辑来思考——见 代码。
那么你的代码违反了局部性原则：在它们所在的地方声明你的变量 需要，而不是其他地方。您还包括非 C++ 标头，此外 不需要。使用 using-directives 只会混淆代码：你再也看不到了 组件来自哪里；而且不需要他们！我还介绍了一个 匿名命名空间，用于更突出的定义。
最后，我使用了更紧凑的编码风格（缩进 2 个空格，括号 同一行，尽可能避免括号。想一想：这样你可以看到很多 一目了然，同时经过一些培训也更容易阅读。
当如图所示编译时，编译器警告 largest_factor possibly used undefined。 事实并非如此，我在这里选择将该警告视为空的。
Program LargestPrimeFactor.cpp:
// Compile with
// g++ -O3 -Wall -std=c++98 -pedantic -o LargestPrimeFactor LargestPrimeFactor.cpp
#include <string>
#include <iostream>
namespace {
const std::string program_name = "LargestPrimeFactor";
const std::string error_output = "ERROR[" + program_name + "]: ";
const std::string version_number = "0.1";
enum ErrorCodes { reading_error = 1, range_error = 2 };
typedef unsigned long uint_type;
const uint_type example = 600851475143; // compile-time warnings will show
// whether uint_type is sufficient
}
int main() {
uint_type number;
std::cout << "Please enter a number to have its largest prime factor found:"
<< std::endl;
std::cin >> number;
if (not std::cin) {
std::cerr << error_output << "Number not of the required unsigned integer"
" type.\n";
return reading_error;
}
if (number <= 1) {
std::cerr << error_output << "Number " << number << " has no largest prime"
" factor.\n";
return range_error;
}
const uint_type input = number;
uint_type largest_factor;
for (uint_type factor = 2; factor <= number/factor; ++factor)
if (number % factor == 0) {
largest_factor = factor;
do number /= factor; while (number % factor == 0);
}
if (number != 1) largest_factor = number;
std::cout << "The largest prime factor of " << input << " is " << largest_factor
<< ".\n";
}
并提供更正。根据您的编译器，您可以尝试使用 unsigned long，看看是否可以得到您的答案。尝试写入 cout 并查看变量是否包含您期望的值。
另一方面，如果您试图找到 最大 因子，从最高可能因子开始倒数不是更有效吗？
您可以将 num 变量声明为 long long int。
long long int num;
这将避免代码中发生的所有类型的溢出！
C++ 程序寻找数的最大质因数。
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
// A function to find largest prime factor
long long maxPrimeFactors(long long n)
{
// Initialize the maximum prime factor
// variable with the lowest one
long long maxPrime = -1;
// Print the number of 2s that divide n
while (n % 2 == 0) {
maxPrime = 2;
n >>= 1; // equivalent to n /= 2
}
// n must be odd at this point
while (n % 3 == 0) {
maxPrime = 3;
n=n/3;
}
// now we have to iterate only for integers
// who does not have prime factor 2 and 3
for (int i = 5; i <= sqrt(n); i += 6) {
while (n % i == 0) {
maxPrime = i;
n = n / i;
}
while (n % (i+2) == 0) {
maxPrime = i+2;
n = n / (i+2);
}
}
// This condition is to handle the case
// when n is a prime number greater than 4
if (n > 4)
maxPrime = n;
return maxPrime;
}
// Driver program to test above function
int main()
{
long long n = 15;
cout << maxPrimeFactors(n) << endl;
n = 25698751364526;
cout << maxPrimeFactors(n);
}
你的问题很有趣！
决定从头开始实现Factorization的两种方法，将整数分解为质因数：
整数 N 的试分法需要
O(N^(1/2)) = O(Sqrt(N))O(N^(1/4)) = O(Sqrt(Sqrt(N)))所以 Pollard Rho 比试验除法快得多，正好是平方倍。
在您在问题中提供的代码中，您也有试分法，但足以运行一个循环直到 Sqrt(N)，而不是像您那样直到 N。所以原来的 Trial Division 方法比你的快得多，因为它在一个循环中花费的时间更少。
这两种方法都在我下面的 C++ 代码中完全实现。在显示带有计时的输出示例的代码之后查看控制台输出。我以 62 位整数为例，它由两个 31 位素数组成。 Pollard Rho 算法比 Trial Division 算法花费的时间少 576x
#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <mutex>
#include <random>
#include <cstdint>
#include <chrono>
#include <cmath>
#include <type_traits>
#include <algorithm>
#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed! Msg: '" + std::string(msg) + "'"); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
#define COUT(code) { std::lock_guard<std::recursive_mutex> lock(cout_mux); std::cout code; std::cout << std::flush; }
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = unsigned __int128;
static std::recursive_mutex cout_mux;
template <typename T> struct DWordOf;
template <> struct DWordOf<u32> : std::type_identity<u64> {};
template <> struct DWordOf<u64> : std::type_identity<u128> {};
template <typename T>
bool IsPrime_TrialDiv(T const & n) {
// https://en.wikipedia.org/wiki/Trial_division
std::vector<T> fs;
if (n <= 16)
return n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13;
if ((n & 1) == 0)
return false;
for (T d = 3; d * d <= n; d += 2)
if (n % d == 0)
return false;
return true;
}
template <typename T>
T PowMod(T a, T b, T const & c) {
using DT = typename DWordOf<T>::type;
T r = 1;
while (b != 0) {
if (b & 1)
r = T((DT(r) * a) % c);
a = T((DT(a) * a) % c);
b >>= 1;
}
return r;
}
template <typename T>
bool IsProbablyPrime_Fermat(T const & n, size_t ntrials = 32) {
// https://en.wikipedia.org/wiki/Fermat_primality_test
if (n < (1 << 14))
return IsPrime_TrialDiv(n);
std::mt19937_64 rng{std::random_device{}()};
std::uniform_int_distribution<T> distr(2, n - 2);
for (size_t i = 0; i < ntrials; ++i)
if (PowMod(distr(rng), n - 1, n) != 1)
return false;
return true;
}
template <typename T>
std::vector<T> Factor_TrialDiv(T n) {
// https://en.wikipedia.org/wiki/Trial_division
std::vector<T> fs;
if (n <= 0)
return fs;
while ((n & 1) == 0) {
fs.push_back(2);
n >>= 1;
}
for (T d = 3; d * d <= n; d += 2)
while (n % d == 0) {
fs.push_back(d);
n /= d;
}
if (n > 1)
fs.push_back(n);
return fs;
}
template <typename T>
T GCD(T a, T b) {
while (b != 0)
std::tie(a, b) = std::make_tuple(b, a % b);
return a;
}
template <typename T>
std::vector<T> Factor_PollardRho(T const & n, size_t ntrials = 8) {
// https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
using DT = typename DWordOf<T>::type;
if (n <= 1)
return {};
if (IsProbablyPrime_Fermat(n))
return {n};
std::mt19937_64 rng{std::random_device{}()};
std::uniform_int_distribution<T> distr(2, n - 2);
for (size_t itry = 0; itry < ntrials; ++itry) {
T x = distr(rng);
bool failed = false;
for (size_t icycle = 1;; ++icycle) {
T y = x;
for (size_t i = 0; i < (1ULL << icycle); ++i) {
x = T((DT(x) * x + 1) % n);
T g = GCD(n + x - y, n);
if (g == 1)
continue;
if (g == n) {
failed = true;
break;
}
ASSERT(n % g == 0);
auto fs0 = Factor_PollardRho(g);
auto fs1 = Factor_PollardRho(n / g);
fs0.insert(fs0.end(), fs1.begin(), fs1.end());
std::sort(fs0.begin(), fs0.end());
return fs0;
}
if (failed)
break;
}
}
ASSERT_MSG(false, "Pollard Rho failed!");
return {};
}
double Time() {
static auto const gtb = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::duration<double>>(
std::chrono::high_resolution_clock::now() - gtb).count();
}
template <typename T>
void Factor(T const & n) {
double tim0 = 0, tim1 = 0;
for (bool method: {true, false}) {
COUT(<< "Method '" << (method ? "TrialDiv" : "PollardRho") << "'" << std::endl);
auto tim = Time();
auto fs = method ? Factor_TrialDiv(n) : Factor_PollardRho(n);
tim = Time() - tim;
if (method)
tim0 = tim;
else
tim1 = tim;
COUT(<< "Time " << std::fixed << std::setprecision(6) << tim << " sec" << std::endl);
COUT(<< "Factors of " << n << " (2^" << std::fixed << std::setprecision(3) << std::log2(n) << ")" << std::endl);
std::sort(fs.begin(), fs.end());
for (auto const & x: fs)
COUT(<< x << " ");
COUT(<< std::endl);
}
COUT(<< "PollardRho boost " << std::fixed << std::setprecision(3) << tim0 / tim1 << "x times" << std::endl);
}
template <typename T>
T RandPrime(T end) {
std::mt19937_64 rng{std::random_device{}()};
std::uniform_int_distribution<T> distr(2, end - 1);
while (true) {
T n = distr(rng) | 1;
if (IsProbablyPrime_Fermat(n))
return n;
}
}
int main() {
try {
using T = u64;
T const n = RandPrime<T>(1ULL << (sizeof(T) * 4 - 1)) * RandPrime<T>(1ULL << (sizeof(T) * 4 - 1));
Factor(n);
} catch (std::exception const & ex) {
COUT(<< "Exception: " << ex.what() << std::endl);
return -1;
}
}
控制台输出：
Method 'TrialDiv'
Time 10.285930 sec
Factors of 2187897340606828307 (2^60.924)
1418549537 1542348211
Method 'PollardRho'
Time 0.017851 sec
Factors of 2187897340606828307 (2^60.924)
1418549537 1542348211
PollardRho boost 576.210x times