ruby -prprime
n=$_.to_i;s=1;(n>>1-n%2).prime_division.map{|a,b|$_=s*=~-a**-~b/a-=1}