We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #179: Consecutive positive divisors
  4. Discussions

Project Euler #179: Consecutive positive divisors

  • urossevkusic
     + 0 comments

    C solution based on an idea from this blog. For some reason, the same idea failed on C++ due to timeout.

    #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    
    unsigned t;
    scanf("%u", &t);
    
    // divisors sieve
    unsigned N = 1e7;
    unsigned *sieve, *pref_sum;
    sieve = (unsigned *) calloc(N + 1, sizeof(unsigned));
    pref_sum = (unsigned *) calloc(N + 1, sizeof(unsigned));
    
    for(unsigned i = 1; i <= N; ++i)
        for(unsigned j = i; j <= N; j += i)
            ++sieve[j];
    
    for(unsigned i = 3; i <= N; ++i)
        pref_sum[i] = pref_sum[i - 1] + (sieve[i] == sieve[i - 1]);
    
    for(unsigned i = 0; i < t; ++i) {
        unsigned k;
        scanf("%u", &k);
        
        printf("%u\n", pref_sum[k]);
    }
    
    free(sieve);
     
    return 0;
}