检查一个数字是否可以表示为两个立方之和的高效程序

我正在尝试编写一个程序来检查数字 N 是否可以表示为两个立方之和，即 N = a^3 + b^3

这是我的代码，复杂度为 O(n)：

#include <iostream>
#include<math.h>
#define ll unsigned long long
using namespace std;

int main()
{
 ios_base::sync_with_stdio(false);
 bool flag=false;
 ll t,N;
 cin>>t;
 while(t--)
 {
     cin>>N;
     flag=false;
     for(int i=1; i<=(ll)cbrtl(N/2); i++)
     {
       if(!(cbrtl(N-i*i*i)-(ll)cbrtl(N-i*i*i))) {flag=true; break;}
     }
     if(flag) cout<<"Yes\n"; else cout<<"No\n";
 }
 return 0;
}

由于代码的时间限制是2秒，这个程序给出了TLE？谁能建议一个更快的方法

我也在 StackExchange 中发布了这个，如果您认为重复，很抱歉，但我真的不知道这些是相同还是不同的板（交换和溢出）。我的个人资料在这里显得不同。

=========================

有一种更快的算法来检查给定的整数是否是两个立方体 n=a^3+b^3 的和（或差）

我不知道这个算法是否已知（可能是，但我在书籍或互联网上找不到它）。我发现并用它来计算整数，直到 n

这个过程使用了一个技巧

4(a^3+b^3)/(a+b) = (a+b)^2 + 3(a-b)^2)

我们事先不知道“a”和“b”是什么，所以“(a+b)”也是什么，但我们知道“(a+b)”肯定应该整除 (a^3+ b^3) ，因此如果您有一个快速素数分解例程，您可以快速计算 (a^3+b^3) 的每个除数，然后检查是否

(4(a^3+b^3)/除数 - 除数^2)/3 = 平方

当（并且如果）找到一个正方形时，您有 divisor=(a+b) 和 sqrt(square)=(a-b) ，因此您有 a 和 b。

如果没有找到平方，则该数字不是两个立方之和。

我们知道除数

现在与其他算法进行一些比较 - 对于 n = 10^18，通过使用暴力，您应该测试所有低于 10^6 的数字才能知道答案。另一方面，要构建 10^18 的所有约数，您需要素数直到 10^9。

10^9 中可以容纳的不同素数的最大数量是 10 (2*3*5*7*11*13*17*19*23*29 = 5*10^9)，所以我们有 2^10-1在最坏的情况下检查素数的不同组合（组合除数），其中许多由于限制而被丢弃。

为了计算素数因子，我使用了一个包含前 60.000.000 个素数的表，该表在此范围内效果很好。

米格尔·贝利利亚