The task itself at first glance seems rather simple:

Find the number of such numbers n (n <10 ^ 5), in which the number of dividers equals the number of dividers of the number n + 1

Here is my solution:

static int NumberOfDividers(int number) { int counter = 0; for (int i = 1; i <= number; i++) if (number % i == 0) counter++; return counter; } static void Main() { int counter = 0; for (int i = 1; i < 100000; i++) { if (NumberOfDividers(i) == NumberOfDividers(i + 1)) counter++; } Console.WriteLine(counter); }

But the algorithm works very long, what are the options to simplify it?

  • one
    The number of numbers n such that n and n+1 have the same number of divisors is infinite ( Roger Heath-Brown (1984) ). If the decomposition of a number into prime factors Product p^e(p) known, then the number of divisors of the number is Product (e(p) + 1) . Here is for testing, an example on Python, which generates natural numbers and their prime factors to find the number of divisors for each number and print the number of numbers for which tau(n) == tau(n+1) . - jfs
  • for example, the result for n<10^6 is 102093 . - jfs

2 answers 2

First, remove the extra calculations from the main loop. Note that at each iteration, you calculate the number of dividers for both numbers, although at each previous iteration, for a smaller number, the value has already been calculated.

 void Main() { int counter = 0; int current = 0; for (int i = 1; i < 100000; i++) { int next = NumberOfDividers(i); if (current == next) { counter++; } current = next; } Console.WriteLine(counter);//10585 }

Only this change will halve the running time.

Now let's deal with the calculation of the number of dividers.

Any number is divisible by 1 and by itself, so we immediately write 2 to the counter, or 0, if it is one.

 static int NumberOfDividers(int number) { int counter = number == 1 ? 0 : 2;

As with primes, it makes no sense to go through all the previous values; it’s enough to go through the values ​​to the root of a given number. If there are dividers smaller than the root, then they will correspond to paired dividers larger than the root.

  double root = Math.Sqrt(number);

If the number is a square, then one of the dividers will be equal to the root, check and add one to the counter, the other dividers are paired. For verification, only the whole part of the root is needed, otherwise when comparing, we will never get equality ( see this question-answer ). In addition, if the initial number is one, this check will add a single divisor to the counter and the function will return 1, as it should.

  int intRoot = (int)root; if(intRoot * intRoot == number) counter++;

Remains the main loop. We start with 2, because the unit and the number itself are already taken into account. Dividers go in pairs, so the counter is increased by 2. The exception is the root of the number, but we have already taken into account.

  for (int i = 2; i < root; i++) if (number % i == 0) { counter +=2;//делители ходят парами. поэтому увеличиваем сразу на два. } return counter; }

After all the manipulations, the total execution time, according to rough measurements *, decreased from ~ 3 minutes to ~ 0.4 seconds. Those. about 450 (!) times.

* The standard test bench did not collect data from the built-in time counter LiNQPad

    I apologize, but pass to C #. But I can sketch on C ++ :)

    So, to calculate the number of divisors - we decompose the number into simple factors; the number of dividers after this is defined as ... as in this answer :) - it is written there.

    It is easy to search for dividers — it suffices to check the primes to the square root of a number, and decreasing the number itself by dividing by the found prime divisor for speed. The quick square root is picked up by Warren in "Algorithmic Stunts"; but you can use regular sqrt .

    We count for each number once, remembering the value for the previous number.

    All, putting it all together -

     #include <iostream> #include <iomanip> #include <map> using namespace std; unsigned int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317 }; inline unsigned long isqrt(unsigned long x) { unsigned long x1, g0, g1; if (x <= 1) return x; int s = 1; x1 = x - 1; if (x1 > 0xFFFF) { s = s + 8; x1 >>= 16; } if (x1 > 0xFF) { s = s + 4; x1 >>= 8; } if (x1 > 0xF) { s = s + 2; x1 >>= 4; } if (x1 > 0x3) { s = s + 1; } g0 = 1ll << s; g1 = (g0 +(x>>s)) >> 1; while( g1 < g0) { g0 = g1; g1 = (g0 + (x/g0)) >> 1; } return g0; } int factors(unsigned long m) { map<int,int> fs; for(unsigned int i = 0; m > 1 && primes[i] <= isqrt(m);) { if (m%primes[i]) { ++i; continue; } m /= primes[i]; fs[primes[i]]++; } if (m > 1) fs[m]++; int count = 1; for(auto q: fs) count *= (q.second+1); return count; } int main(int argc, const char * argv[]) { int total = 0, last = 1; for(unsigned long n = 2; n < 100000; ++n) { int count = factors(n); if (last == count) { // cout << (n-1) << " vs " << n << " count = " << count << endl; ++total; } else last = count; } cout << total; }

    Counts in milliseconds - see https://ideone.com/QRI81U

    Once again, I apologize for C ++, not C # ...

    • Here is a translation in C # ideone.com/tI8ayc . If you believe the timer ideon, then even a little faster than the worked on the pluses =) but I think this is a simple error. An interesting solution, I liked it, though I had to figure out how std :: map works, in order to make a correct replacement for the Dictionary, it does not know how to add elements when accessing the missing one. Well, the types had to be cut a little, otherwise the horror with ghosts begins there. - rdorn