c - Number of pairs (a, b) such that a*b < N where a, b, N are integers greater than 0 -


i have code in c calculate number of such pairs::

long long factors(int n) {     int nr = (int) sqrt(n);     int b;      int fix = n - nr * nr - 1;     long long ans = 0;     (b = 2; b <= nr; b++) {         if (n % b == 0) {             ans += n/b - 1;         } else {             ans += n/b;         }     }      if ( fix < 0) {         ans = (2*ans) + n + fix;     } else {         ans = (2*ans) + n + fix - 1;     }      return ans;  }

this function correctly computes number of such pairs. logic behind it?

illustrative diagram

consider following illustration of case n = 10, each position represents pair of factors counted, a/n, 2 , -/* show stages of algorithm when pair counted (as explained below) , . placeholder mark pairs not counted in stage in question:

  | 1   2   3   4   5   6   7   8   9 --+-~~~-===-===----------------------- 1 ! n2- a2- a2- .2. .2. .2. .2. .2. .2. 2 ! n2- a2- a2- .2. 3 ! n2- a2- a2* 4 | n.. a.. 5 | n.. 6 | n.. 7 | n.. 8 | n.. 9 | n..

explanation of algorithm

what algorithm does, is:

  • count columns 2 int (sqrt (n)) (i.e. 3 in above case, marked = , a).
    • column b adds n / b unless b factor of n, in case last not count.
  • add n - 1 first column (marked ~ , n).
  • double this, cover yet uncounted rows (marked ! , 2).
  • subtract region counted twice (marked -), has size nr2, or 1 less if nr2 = n, in case not have counted (nr,nr) (marked * instead of -).

the calculation of fix , last part of code (and ) may rearranged follows, if eliminate calculation , test of fix:

    ans = ans + n - 1;              // add in first column     ans = 2 * ans;                  // double cover rows      if ( nr * nr != n )             // equivalent fix >= 0         ans = ans -  nr * nr;       // subtract square region counted twice     else         ans = ans - (nr * nr - 1);  // did not count (nr,nr)

commented code

the posted code, mildly adapted (assuming c99 / msvs 2012+) , commented:

long long factors(int n) {     long long ans = 0;        // result return     int nr = (int) sqrt(n);   // highest possible value of lower factor      // count factorisations (a,b) ∈ 2..√n     (int b = 2; b <= nr; b++) {         if (n % b == 0) {    // if b | n ..             ans += n/b - 1;  // .. b*(n/b) = n, count 1..(n/b - 1)         } else {             ans += n/b;      // .. count 1..n/b         }     }      // remaing steps of algorithm, optimised:     // - add n-1 1st column (1,1..(n-1)), giving total (a,b) ∈ 1..√n     // - double, cover reversed pairs (b,a) ∈ 1..√n, b ∈ √n..n     // - subtract nr² or nr²-1, pairs counted twice     int fix = n - nr * nr - 1;     // correcting term, chosen compare 0     if ( fix < 0) {                   // i.e. if nr² = n ..         ans = (2*ans) + n + fix;      // .. ans = 2*(ans + n-1) - (nr² - 1)     } else {         ans = (2*ans) + n + fix - 1;  // .. ans = 2*(ans + n-1) - (nr²)     }      return ans;  }

Comments

Post a Comment

Popular posts from this blog

angularjs - ADAL JS Angular- WebAPI add a new role claim to the token -

i have created angular spa webapi backend using adal js authentication.as there no roles in ad, need manually add role claims in order give users access different api controllers. the roles stored in database. expecting inject claim through call webapi after authentication ad. webapi code might this. identity.addclaim(new claim("role", "user")); var ticket = new authenticationticket(identity, props); var accesstoken = startup.oauthbeareroptions.accesstokenformat.protect(ticket); is possible replace adal idtoken new token? is viable solution or there other better way handle this? as initial token generated azuread, possible edit token add new claim? appreciated. graph api supporting group claims. see here: http://justazure.com/azure-active-directory-part-4-group-claims/ if @ examples on page, users assigned groups , app can check group in claims. in current version of portal, need app manifest , modify it.
Read more

node.js - Using Node without global install -

i'm working on few node & electron (atom shell) projects , i'm curious how them work without user having install node globally. i've seen few applications including node directory in project contains node.exe binary. how go setting node project use binary? edit: thought should add, i've searched everywhere answer this, unrelated results.
Read more

php - CakePHP HttpSockets send array of paramms -

i problem when make request (i can request). $link = 'http://uri/path/?param1=1&sid=2&sid=3&sid=4' $http = $httpsocket = new httpsocket(); $res = $httpsocket->get($link); if check request pr($http); i see : [line] => /url/path/?param1=1&sid%5b0%5d=2&sid%5b1%5d=3&sid%5b2%5d=4 http/1.1 and i'm getting empty response because server doesn't know parameters sid%5b0%5d=2 when try send parameters array : $data = array('param1' => '1', 'sid' => array('2','3', '4')); i see same changes %5b0%5d - additional indexes. how fix it? unfortunately , can not change server side, if send request in browser, i'll normal response in json format. when make request, can parameters this: $param1 = $_get['param1']; $sid= $_get['sid']; tip: use diferente names parameters. have multiples sid. use sid1, sid2, sid3... update: can parameters this:...
Read more