Factoring large numbers into triplets

I've found similar questions but this is a bit more complicated.

I have a large number n(I actually have more, but it doesn't matter now), (>40 digits), and I want to find a*b*c=n triplets. n's prime factorisation is done. It has no large prime divisors, but many of small prime divisors. The sum of all prime divisors (included multiple divisors) is greater than 50.

I'd like to find a*b*c=n triplets, where a<=b<=c. I don't want all the triplets, because there are too much of them. I'm searching for special ones.

For example:

the triplet(s) where ca is minimal,

the triplet(s) where c/a minimal,

the one where a,b and c has the maximal common divisor,

these conditions combined.

This can be a little easier to solve if we know that n=k!(factorial). Solving could lead to a general method. Computing all these triplets with brute force is not an option because of the size of n, so i need a good algorithm or some special tools to help me implement a solution for this.

Sorry for my bad English,

Thanks for the answers!

---

You can achieve it with a simple, O(|D|^2) algorithms, where D is an ordered list of all the numbers dividing n , which you already have.

Note that you only have to find a,b , because c=n/(a*b) , so the problems boils down to finding all the pairs (a,b) in D so that a<b and n/(a*b) ∈ D .

Pseudocode:

result = empty_list
for (int i=0; i<D.size-1, i++) {          // O(|D|)
    for (j=i+1; j<D.size, j++) {          // O(|D|)
         a, b = D[i], D[j]
         c = n/(a*b)
         if (D.contains(c) && c>b) {      // O(1)
             result.append( (a,b,c) )
         }
    }
}                                         // O(|D|)*O(|D|)=O(|D|^2)

---

I might have the solution, but I have no time to implement it today. I write it down, so maybe somebody will agree with me or will spot the weak point of my algorithm.

So let's see the first or second case, where c/a or ca should be minimal.

1: In first step I split the prime factors of n to 3 group with a greedy algorithm. I will have an initial a,b and c and they will be not very far from each other. The prime factors will be stored in 3 arrays: a_pf,b_pf,c_pf.

2: In next step I compute all the possible factors for a,b and c, I store them in different arrays, then I order these arrays. These will be a_all,b_all and c_all.

3: I compute q=max(a,b,c)/min(a,b,c). (now we can say that a is the smallest, c is the greatest number)

4: I search a_all and c_all for numbers on this condiition: c_all[i]/a_all[j] < q. When I find it, I change the prime factors of these values in a_pf and c_pf. With this method, the largest and the smallest member of the triplet will come closer to each other.

I repeat step 2-3-4, until I can. I think this will end after finite number of steps.

Since the triplet's members are smaller than the original n, I hope this solution will give me the correct triplet at most in a few minutes.

链接地址: http://www.djcxy.com/p/61380.html

上一篇: 机器学习/数据挖掘中的内存太慢或内存不足问题

下一篇: 将大数分解为三元组