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.