Pretty basic right? #2

Let $N=4\times 10^7$ . By a simple double-counting argument, we have $\sum_{i=2}^{N}\sigma_0(i)= \bigg(\sum_{i=1}^{N}\lfloor \frac{N}{i}\rfloor\bigg) -1$ Details : We evaluate the sum by counting the number of multiples of a number $i$ upto the number $N$ . Clearly it has $\lfloor \frac{N}{i} \rfloor$ multiples.

C++!

$\mathbf{Solution 1 \; \; : }$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

 #include <iostream>
using namespace std;

int main() {
 unsigned long int i,k,n,sum=0;
   for(unsigned long int x=2;x<=40000000;x++)
 { 
    n=x;
    k=0;
 for(i=1;i*i<n;i++)
   {  
     if(n%i==0)
      k++;
   }
     k=k*2;
     if(i*i==n)
      k++;
   sum+=k
 }
   cout<<sum; 
    return 0;
}

$\mathbf{Solution 2 \; \; : }$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>
using namespace std;

int main() {

unsigned long int n,sum=0,t;

  for(unsigned long int x=1;x<=40000000;x++)
     { 
        t=(40000000/x);
     sum+=t;
             }
      cout<<sum-1;       
    return 0;
}

Out of these two programs I would prefer the second one. The first one takes a long time for compilation, whereas the second is short and sweet!

Using PARI/GP where it would be better to use one's head.

1
2
3
4
5
6
7

(13:xx) gp > primelimit=10^8
%1 = 100000000
(13:xx) gp > total=0
%2 = 0
(13:xx) gp > for (i=2,4*10^7,total+=length(divisors(i)))
(13:xx) gp > print (total)
706353001