TOTIENT FUNCTIONS MODIFICATION

Can anybody suggest me an efficient algorithm for finding the number of numbers <=‘m’ which are relatively co-prime to ‘n’.

Hi anupam,

for finding number of co-prime number not exceeding m first you have to factorize m into its prime power then you can apply totient function. have a look http://2000clicks.com/mathhelp/NumberTh04Totient.aspx
if you have any doubt then you can ask :slight_smile:

Refer to the solution- http://ideone.com/InlDBv. You can try yourself with any input value for n and m in int range.

@admin123 I think you misunderstood my question. you gave me the solution of finding no of nos <= M and co-prime to IT, but my question was no of nos<= M and co-prime to N

There is no runtime error. It is shown as there is no input value for n and m. So array size is not available. So it is giving runtime error. I have checked the code on my PC. If the problem is solved, mark it. Hope it helped.

what if m is around 10^9. an array of that size will lead to runtime error

what are the ranges of n and m? my code complexity will time out for m,n>10^5

only after ranges are provided we can think about complexity and other memory related problems.