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.