# 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

eg:N=6

x=1 y1=6

x=2 y2=3

.

.

.

x=6 y6=1

sum=y1+y2+y3…+y6

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.

solution:

``````ans=0,result=0;
for(i=1;i<=floor(n/2);i++)
ans=ans+n/i;

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 …
sum=0;
for(i=1;i*i<=N;i++)
{

if(N%i==0)
{
sum+=i+N/i;
}
}
if(i*i==N) sum-=i;

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

actually its the logic of the question:http://www.codechef.com/problems/COOLGUYS
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.
Keep helping the guys.

how did u get 6 3 2 1 1 1…
its

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

@shivam9753…thank you brother…