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.
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.
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.
Thank you. Got AC.