减少整数分数算法
（这源于最近完成的编程竞赛）
您将获得两个10 ^ 5整数的数组，范围为1..10 ^ 7，包括：
int N[100000] = { ... } int D[100000] = { ... } 想象一下，有理数X是将N的所有元素相乘并除以D的所有元素的结果。
修改两个数组而不更改X的值（并且不指定任何元素超出范围），使得N的乘积和D的乘积没有公因子。
一个天真的解决方案（我认为）会起作用……
for (int i = 0; i < 100000; i++) for (int j = 0; j < 100000; j++) { int k = gcd(N[i], D[j]); // euclids algorithm N[i] /= k; D[j] /= k; }
……但这太慢了。
什么是少于10 ^ 9次操作的解决方案？
将所有数字分解为1到10 7 。 使用Eratosthenes筛子的修改，你可以将 比这更好的可能是创建一个只有最小的素因子的数组。 O(n*log n)时间内的所有数字从1到n分解（我认为它有点好， O(n*(log log n)²)或者左右）使用O(n*log log n)空间。
// Not very optimised, one could easily leave out the even numbers, or also the multiples of 3 // to reduce space usage and computation time int *spf_sieve = malloc((limit+1)*sizeof *spf_sieve); int root = (int)sqrt(limit); for(i = 1; i <= limit; ++i) { spf_sieve[i] = i; } for(i = 4; i <= limit; i += 2) { spf_sieve[i] = 2; } for(i = 3; i <= root; i += 2) { if(spf_sieve[i] == i) { for(j = i*i, step = 2*i; j <= limit; j += step) { if (spf_sieve[j] == j) { spf_sieve[j] = i; } } } }
使用该筛子将n > 1因子分解，查找其最小的素因子p ，确定其在n的因子分解中的多重性（通过递归查找，或者通过简单地划分直到p不均匀地划分剩余的辅助因子，更快取决于）和辅助因子。 当辅助因子大于1时，查找下一个主要因子并重复。
创建从素数到整数的映射
遍历两个数组，对于N每个数字，将其因子分解中每个素数的指数加到地图中的值，对于D的数字，减去。
遍历地图，如果素数的指数为正，则将p^exponent输入到数组N （如果指数太大，则可能需要将其分割为多个指数;对于较小的值，将几个素数合并为一个条目- 有664579个质数小于10 7 ，所以数组中的100,000个插槽可能不足以用正确的功率存储每个出现的素数），如果指数为负，则对D数组执行相同操作，如果它为0，忽略那个素数。
然后将N或D中任何未使用的槽设置为1。
对每个元素的每个元素进行分解，排序，取消。 因子分解是有界大小的整数的恒定时间，排序是n log n，并且取消将是线性的。 但是，常数因素可能很大。
如果你试图降低实际执行时间而不是更低的渐近复杂度，那么通过手动取消小因子（例如2,3,5和7的幂）来预处理数组可能不会有什么坏处。具有高概率（即除了病理输入外，这将大大加速大多数算法，代价是几次线性时间的传递。
集成上述方法的另一种更复杂的方法是首先构建一个最大为sqrt(10^7) ~= 3162的素数列表。 根据素数定理，应该有大约3162/ln(3162) ~= 392这样的素数。 （事实上，为了节省运行时间，你可以/应该预先计算这个表。）
然后，对于N每个这样的整数，并且对于每个素数，通过该素数减少整数，直到它不再均匀地分开，并且每次递增该素数的计数。 对D做同样的事情，而不是递减。 一旦你通过了素数表，当前的int将是非-1，当且仅当它是一个大于3162的素数时。这应该是每个数组中总数的7％左右。 你可以将它们保存在一堆或某些东西中。 随着你的进展，也将它们设置为arrays中的那些。
最后，你迭代积极因素并将他们的产品放入N.你可能需要将它分成多个数组插槽，这很好。 将负面因素放入D，你就完成了！
这个运行时间需要一分钟才能完成。 希望这是合理的。
让我们将N和D中的每个元素分解为O（sqrt（10 ^ 7）* 10 ^ 5）as
N[i]=p1^kn1 * p2^kn2 ... D[i]=p1^kd1 * p2^kd2 ...
维护2个电源arrays
Power_N[p1]=sum of kn1 for all i's Power_D[p1]=sum of kd1 for all i's Divide the N and D by p1^(min(Power_N[p1],Power_D[p2])) in O(10^5) each
几乎所有的东西都写完了，我建议让p =（N中所有元素的乘法）
设q =（D中所有元素的乘法）
X =（P / Q）; 应始终保持不变
找到p，q的素因子;
通过可能将其功率存储在矩阵a [0]（2的幂），a [1]（3的幂），a [2]（5的幂）等等中。 现在，您可以比较矩阵中的值，并将较低值的幂降低到零。
例如。 p = 1280 q = 720
对于pa [0] = 8（2的幂）a [1] = 0（幂3）a [2] = 1（幂为5）;
对于qb [0] = 4 b [1] = 2 b [2] = 1;
使一个/两个（如果两者相等）值/ s为索引0,1,2 …….