在开始之前，我想说：这不是作业，只是单纯的、有趣的事情。
现在，我正在尝试设计一个算法来回答这个问题1/x + 1/y = 1/n!。
正如您可以从上面的链接看到的那样，作者只要求提示，而不是实际答案，所以我也想请求同样的待遇。
我简化了表达式，直到(x - n!) (y - n!) = (n!)^2，就像其中一个答案所建议的那样，那时我明白了(x,y)对的组合数与n!^2的因子数相同（如果我理解错误，请纠正我）。
所以，就像被接受的答案所建议的那样，我正在尝试获得N！^2的每个质数因子的所有因子的乘积。
我使用C语言编写了一些代码，使用试除法分解N!^2，并使用埃拉托斯特尼筛法获取sqrt(N!^2)以下的所有质数。
现在的问题是内存，我尝试了N = 15，但我的Mac（四核6GB内存）几乎死机。问题出在内存上。因此我添加了一些printf并尝试了N = 11：
这个列表包含了N!^2的所有质因数（当然不包括1和N!^2本身）。
我希望能够得到一些关于如何减少内存消耗以及可能的优化方案的提示。
下面是代码，仅仅是一个快速实验，所以我相信它可以被优化。
现在，我正在尝试设计一个算法来回答这个问题1/x + 1/y = 1/n!。
正如您可以从上面的链接看到的那样，作者只要求提示，而不是实际答案，所以我也想请求同样的待遇。
我简化了表达式，直到(x - n!) (y - n!) = (n!)^2，就像其中一个答案所建议的那样，那时我明白了(x,y)对的组合数与n!^2的因子数相同（如果我理解错误，请纠正我）。
所以，就像被接受的答案所建议的那样，我正在尝试获得N！^2的每个质数因子的所有因子的乘积。
我使用C语言编写了一些代码，使用试除法分解N!^2，并使用埃拉托斯特尼筛法获取sqrt(N!^2)以下的所有质数。
现在的问题是内存，我尝试了N = 15，但我的Mac（四核6GB内存）几乎死机。问题出在内存上。因此我添加了一些printf并尝试了N = 11：
Sieve of Eratosthenes took 13339.910000 ms and used 152 mb of memory
n= 11; n!^2 = 1593350922240000; d = 6885
[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,5,5,5,5,7,7,11,11]
这个列表包含了N!^2的所有质因数（当然不包括1和N!^2本身）。
我希望能够得到一些关于如何减少内存消耗以及可能的优化方案的提示。
下面是代码，仅仅是一个快速实验，所以我相信它可以被优化。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <strings.h>
#include <sys/time.h>
#include <assert.h>
//Linked List
struct node {
struct node * next;
long val;
};
void addValue(struct node *list, long val) {
struct node *n = list;
if (n->val == -1) {
n->val = val;
return;
}
while (n->next) {
n = n->next;
}
struct node *newNode = malloc(sizeof(struct node));
newNode->val = val;
newNode->next = NULL;
n->next = newNode;
}
void freeLinkedList(struct node *list) {
struct node *c = list;
if (!c) return;
struct node *n = c->next;
free(c);
freeLinkedList(n);
}
void printList(struct node *list) {
struct node *n = list;
printf("[");
while (n) {
printf("%ld", n->val);
n = n->next;
if (n) {
printf(",");
}
}
printf("]\n");
}
//-----------
int fac(int n) {
if (n == 1) return 1;
return fac(n-1)*n;
}
//Sieve of Eratosthenes
int sieve_primes(long limit, long **list) {
struct timeval t1;
struct timeval t2;
double elapsedTime = 0;
gettimeofday(&t1, NULL);
assert(limit > 0);
//Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
long arrSize = limit-1;
long *arr = malloc(sizeof(long)*arrSize);
long c = 2;
for (long i = 0; i < arrSize; i++) {
arr[i] = c++;
}
assert(arr[arrSize-1] == limit);
for (long i = 0; i < arrSize; i++) {
//Let p be equal to the first number not crossed
long p = arr[i];
if (p == 0) continue;
//Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list.
for (long f = p+p; f < arrSize; f+=p) {
arr[f] = 0;
}
}
*list = arr;
gettimeofday(&t2, NULL);
elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0; // sec to ms
elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0; // us to ms
printf("Sieve of Eratosthenes took %f ms and used %lu mb of memory\n",elapsedTime, (arrSize * sizeof(int))/1024/1024);
return arrSize;
}
void trial_division(struct node* list, long n) { if (n == 1) {
addValue(list, 1);
return;
}
long *primes;
long primesSize = sieve_primes(sqrt(n), &primes);
struct timeval t1;
struct timeval t2;
double elapsedTime = 0;
gettimeofday(&t1, NULL);
for (long i = 0; i < primesSize; i++) {
long p = primes[i];
if (p == 0) continue;
if (p*p > n) break;
while (n % p == 0) {
addValue(list, p);
n/=p;
}
}
if (n > 1) {
addValue(list, n);
}
free(primes);
}
int main(int argc, char *argv[]) {
struct node *linkedList = malloc(sizeof(struct node));
linkedList->val = -1;
linkedList->next = NULL;
long n = 11;
long nF = fac(n);
long nF2 = nF*nF;
trial_division(linkedList, nF2);
long multOfAllPrimeFactors = 1;
struct node *c = linkedList;
while (c) {
long sumOfVal = 2;
long val = c->val;
c = c->next;
while(c) {
long val2 = c->val;
if (val == val2) {
sumOfVal++;
c = c->next;
} else break;
}
multOfAllPrimeFactors*=sumOfVal;
}
printf("n= %ld; n!^2 = %ld; d = %ld\n", n,nF2, multOfAllPrimeFactors);
printList(linkedList);
freeLinkedList(linkedList);
}
编辑:
举个例子，我将展示如何计算初始方程的所有可能正整数解：
3!^2 = 36 = (3^2*2^2*1^0)
因此，对于这个二次不定方程，有(1+2)(1+2)(1+0)=9种可能的正整数解。如果计算负整数，则数量翻倍。我使用 WolframAlpha 来确保。
编辑2:
我想我刚刚找到了“阶乘是什么”，我得到了这个非常有趣的输出：
3! = [2,3]
3!^2 = [2,2,3,3]
3!^3 = [2,2,2,3,3,3]
3!^4 = [2,2,2,2,3,3,3,3]
谢谢 :D