Golu and Sweetness | CodeChef

can someone help me figure out how to reduce time complexity for the question as it doesnot have editorial

make a program to print all the numbers with a prime sweet factor from 0 to 10^4. You’ll definitely see a pattern. Alternatively you can look up totient function, specifically the fact that it is multiplicative.

1 Like

thanks i got the first hint and got ac but not able to understand for totient. can you please add some more information about that.Thanks

Go to “other formulae”. The first few should be enough to prove it.

1 Like

is there only one pattern that 3,5,6 will only give prime totient others will not???

Yes that’s almost correct. I think you meant to type 4, not 5.

yeah ,sorry

Thank you. Got AC.