How to find if a number in the list being the product of other two numbers?-CodePudding

I am trying to find whether any number (in a list with numbers from 1 to 100000) can be the product of other two numbers in the list. If so, they can form a group.
For example, 6 = 2 x 3, hence 2, 3, 6 can form a group.
Therefore, my current method is to first divide the list into 3-membered lists, hence check whether each group is valid. If it is valid, the largest number in the group is stored in the list "maxs". If not, the system omits it.
After checking all the groups, I would like to print the maximum value in "maxs".
Therefore, I have the following code.

import itertools
rans = list(range(1, 10 ** 5))

all_com = []
maxs = []
for ran in rans:
    coms = itertools.combinations(rans,3)
    coml = list(coms)
    all_com  = coml
for com in all_com:
    com = [int(n) for n in com]
    if com[0] == com[1] * com[2] or com[1] == com[0] * com[2] or com[2] == com[0] * com[1]:
        maxs.append(max(com))
print(max(maxs))

Although it could be run, it becomes a huge RAM eater and even broke Google Colab. Also, the code is too slow.
May I know if there is a way to prevent this trial from overloading any RAMs or even a faster method to do the same thing? Thank you!

CodePudding user response：

So I ended up with that

import random

rans_dict = {k: None for k in list(set([random.randint(1, 100000) for i in range(100000)]))}

for key, value in rans_dict.items():
    for i in range(2, int(key ** 0.5)   2):
        if key % i == 0 and key // i in rans_dict:
            rans_dict[key] = (i, key // i)

print(rans_dict[232])

So i used dict for O(1) access (to speed up). Then I just checked each number for factors (O(nlogn)) and if both divisor and qoutient are in dict (so there is O(1) dict keys is used). Then you add them to dict values.

CodePudding user response：

This should be faster and take less RAM.

If i understand correctly we are only interested in the product of two numbers. So we can use for j in rans[i-1:] to remove 50% of all tests (3 * 2 = 6 and 2 * 3 = 6 is the same, so we only need to check 3 * 2)

rans = list(range(1, 10 ** 5))
maxrans = max(rans)
maxs = set()
for i in rans:
    for j in rans[i-1:]: # We don't need to check 3*2 if we have checked 2*3
        tmp = i*j
        if tmp < maxrans: # i*j can't be bigger than 10 ** 5
            maxs.add(tmp)
        else:
            break
print(max(maxs))