Finding The sum of The Number Of multiples of x where the multiple varies from x to N

suppose N is given to us.We need to find the sum of the number of multiples of x where x starts from x=1 to x=N and the multiple(let it be m) varies from x<=m<=N


x=1 y1=6

x=2 y2=3




x=6 y6=1


what is the best method to do it as the number i.e N can be very large i.e it can be in the order of 10^9

it can be solved in linear time(n/2) with certain division operation.
Will it be a problem.?

you just need n/2 iteration.

I dont think direct formula can be derived, because it includes summmation of harmonic series upto n.

@aniruddha paul.



res=ans+ ceil(n/2);

@aniruddha_paul but N is order of 10^9…N/2 is not much optimized to do this question…
u can do this in sqrt(N)…just through 1 to sqrt(N)…if i%N==0 than there are two factor of N : i and N/i…you can get all the factor of N in root(N)…only extra condition to look only when i and N/i will become same in that case it will be add twice for correct this u need u check only if number is proper square of any number than subtract that number from sum and u will get desired output…hope it is clear …

if(i*i==N) sum-=i;

you can optimize it to sqrt(n).
As rcsldav2017 said.

actually its the logic of the question:
But in the editorial They have used an approach which I m not getting it.
Plz help me out.

How?For carrying the multiplication starting from 1—>N its is O(n)
and N is 10^9.

How are you getting harmonic series over here.??
according to the eg above
6 3 2 1 1 1
is ii a harmonic series???

@shivam9753…m i right??

Yes brother. :slight_smile:
Keep helping the guys.

how did u get 6 3 2 1 1 1…

6*(1+(1/2)+(1/3))+ n/2;

@shivam9753…thank you brother…