We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.

Return to Revisions

Haskell, (削除) 106 (削除ここまで) 104 bytes

c x=2/=sum[1|0<-mod x<$>[1..x]]
[]%n=[]
(x:r)%n|c x,(d,m)<-divMod n x,c d,m<1=x:g d|1<3=r%n
g n=[4..n]%n

Try it online!

Less golfed and explanation:

c x = 2 /= sum[1|0<-map(mod x)[1..x]] -- counts number of divisors of x and returns true for all non-primes
g n = f [4..n] n -- call f with a list of factor candidates and n
f [] n = [] -- if there are no factor candidates, return the empty list
f (x:r) n -- for the factor candidate x ...
 | c x, -- check if x is composite
 (d,m) <- divMod n x, -- set d = n div x and m = n mod x
 m < 1, -- n is divided by x if m = 0
 c d -- check that d is composite or 1
 = x : f (x:r) d -- if all those checks are true append x to the list and determine the composites for d
 | otherwise = f r n -- otherwise check the next candidate