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. Prepare
  2. Mathematics
  3. Fundamentals
  4. Sherlock and Divisors
  5. Discussions

Sherlock and Divisors

Sort by

recency

|

168 Discussions

|

  • venom1724
     + 0 comments

    Python golfing, 3 lines, O(sqrt(n))

    divs = {i for i in range(2,int(math.sqrt(n))+1) if n%i==0}
divs|= {n//i for i in divs}|{n}
return sum(not i&1 for i in divs)

    Bonus optimizations with bithacks which bring down runtime a lot but still same asymptotic worst case:

    twos, n = (n&-n).bit_length()-1, n//(n&-n)
divs = {i for i in range(3,int(math.sqrt(n))+1,2) if n%i==0}
divs|= {n//i for i in divs}
return twos+twos*(n!=1)+len(divs)*twos

    The idea is to first extract the number of 2 factors from N, then find the number of factors of the now-odd N and do some basic combinatorics to come up with the answer.

  • rowlandwebb
     + 0 comments

    c#

    public static int divisors(int n)

    {
    int divisors = 0;
    if (n % 2 != 0)
    {
        return divisors;
    }
    else for (int i = 1; i <= Math.Floor(Math.Sqrt(n/2)); i++)
    {
        if ((n/2) % i == 0)
        {
            divisors++;
            if (i*i != n/2)
            {
                divisors++;
            }
        }
    }
    return divisors;
}

  • thefdownloader
     + 0 comments

    great

  • Sashz_MX8
     + 0 comments

    Python 3

    def divisors(n):
    c2 = 0
    p = 1

    while p * p <= n:
        if n % p == 0:
            if p % 2 == 0:
                c2 += 1
            if p != n // p and (n // p) % 2 == 0:
                c2 += 1
        p += 1

    return c2

    Java 8

       public static int divisors(int n) {
        int c2 = 0;
        int p = 1;
        while (p * p <= n) {
            if (n % p == 0) {
                if (p % 2 == 0) c2++;
                if (p != n / p && (n / p) % 2 == 0) c2++;
            }
            p++;
        }
        return c2;
    }

  • duongduchuyaz
     + 0 comments
    def divisors(n):
    # Write your code here
    if n%2 == 1:
        return 0
    
    ans = 0
    n = int(n/2)
    for i in range(1, int(math.sqrt(n)+1)):
        if n % i == 0 and i**2 != n:
            ans += 2
        if i**2 == n:
            ans += 1
    return ans