title: greatest divisor of a number and prime factors relation
body: <p>Question is as follows :
  Given two numbers n and k. For each number in the interval [1, n], your task is to calculate its largest divisor that is not divisible by k. Print the sum of all these divisors.
  Note: k is always a prime number.
  t=3*10^5,1&lt;=n&lt;=10^9, 2&lt;=k&lt;=10^9</p>
  
  <p>My approach toward the question:
  for every i in range 1 to n, the required divisors is i itself,only when that i is not a multiple of k.
  If that i is multiple of k, then we have to find the greatest divisor of a number and match with k. If it does not match, then this divisor is my answer. otherwise, 2nd largest divisor is my answer.</p>
  
  <p>for example,take n=10 and k=2, required divisors for every i in  range 1 to 10 is 1, 1, 3, 1, 5, 3, 7, 1, 9, 5. sum of these divisors are 36. So ans=36.</p>
  
  <p>My code,which works for a few test cases and failed for some.</p>
  
  <pre><code>#include&lt;bits/stdc++.h&gt;
  using namespace std;
  #define ll long long int
  
  ll div2(ll n, ll k) {
  if (n % k != 0 || n == 1) {
      return n;
  }
  
  else {
      for (int i = 2; i * i &lt;= n; i++) {
          if (n % i == 0) {
              ll aa = n / i;
              if (aa % k != 0) {
                  return aa;
              }
          }
      }
  }
  return 1;
  }
  
  
  
  int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin &gt;&gt; t;
  
  while (t--) {
      ll n, k;
      cin &gt;&gt; n &gt;&gt; k;
      ll sum = 0, pp;
  
      for (pp = 1; pp &lt;= n; pp++) {
          //cout &lt;&lt; div2(pp, k);
          sum = sum + div2(pp, k);
      }
      cout &lt;&lt; sum &lt;&lt; '\n';
   }
  
   }
  </code></pre>
  
  <p>Can someone help me where I am doing wrong or suggest me some faster logic to do this question as some of my test cases is showing TIME LIMIT EXCEED</p>
  
  <p>after looking every possible explanation , i modify my code as follows:</p>
  
  <pre><code>#include&lt;bits/stdc++.h&gt;
  using namespace std;
  #define ll long long int
  
  int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin &gt;&gt; t;
  
  while (t--) {
      ll n, i;
      ll k, sum;
      cin &gt;&gt; n &gt;&gt; k;
  
      sum = (n * (n + 1)) / 2;
  
      for (i = k; i &lt;= n; i = i + k) {
          ll dmax = i / k;
  
          while (dmax % k == 0) {
              dmax = dmax / k;
          }
          sum = (sum - i) + dmax;
  
      }
      cout &lt;&lt; sum &lt;&lt; '\n';
  
  }
  
  }
  </code></pre>
  
  <p>But still it is giving TIME LIMIT EXCEED for 3 test cases. Someone please help.</p>