import itertools
def factors(n):
result = set()
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
result.add(i)
result.add(n // i)
return sorted(result)
def main():
n = 108
factors_list = factors(n)
triplets = []
for a_idx in range(len(factors_list) - 2):
a = factors_list[a_idx]
for b_idx in range(a_idx + 1, len(factors_list) - 1):
b = factors_list[b_idx]
for c_idx in range(b_idx + 1, len(factors_list)):
c = factors_list[c_idx]
if a * b * c == n and a < b < c:
triplets.append((a, b, c))
print("All ways in which three distinct positive integers have a product of 108:")
for triplet in triplets:
print(triplet)
if __name__ == "__main__":
main()
Run:
-▶ python a.py
All ways in which three distinct positive integers have a product of 108:
(1, 2, 54)
(1, 3, 36)
(1, 4, 27)
(1, 6, 18)
(1, 9, 12)
(2, 3, 18)
(2, 6, 9)
(3, 4, 9)
Too smart for its own good, maybe? Still, apparently correct on the first try.
There's an import for `itertools` which isn't used, just as noted in the article for 4o.
Can someone who knows what it's about say how optimal this version is, compared to other answers?
Algorithmically it is optimal, many corner cases thought of to make as few loops as possible.
But it is suboptimal in the sense that it uses for loops so it is not possible for an underlying engine to execute in parallel, or to optimize the looping in native (e.g. C) code.
In short - the for loops are 'how'. Without loops it is much more 'what' which leaves it up to the computer to optimize
% Define a predicate to find all positive divisors of N
divisors(N, Divisors) :-
findall(D, (between(1, N, D), N mod D =:= 0), Divisors).
% Define a predicate to generate all combinations of three distinct elements from a list
combination3(List, X, Y, Z) :-
select(X, List, Rest1),
select(Y, Rest1, Rest2),
select(Z, Rest2, _),
X < Y, Y < Z.
% Define a predicate to find triplets (X, Y, Z) such that X*Y*Z = N
find_triplets(N, X, Y, Z) :-
divisors(N, Divisors),
combination3(Divisors, X, Y, Z),
X * Y * Z =:= N.
% Define a predicate to list all the triplets
list_triplets(N) :-
findall((X, Y, Z), find_triplets(N, X, Y, Z), Triplets),
writeln(Triplets).
I'm in love. I both understand what is happening (I think I would understand it even if I didn't know the task description!) and could easily port optimizations from the previous solution.
Maybe this is the point when being a polyglot developer - knowing tens of programming languages and their characteristics - will finally start paying off.
There's an import for `itertools` which isn't used, just as noted in the article for 4o.
Can someone who knows what it's about say how optimal this version is, compared to other answers?