Given the number N. Find from the range from 1 to N the number with the maximum sum of dividers (including non-simple dividers, 1 and the number itself). If there are several such numbers, output any of them. Pascal ABC.

Closed due to the fact that off-topic participants awesoon , null , VenZell , fori1ton , Andrei Arshinov 8 May '15 at 8:58 .

  • Most likely, this question does not correspond to the subject of Stack Overflow in Russian, according to the rules described in the certificate .
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • @ nadegda-sp, According to the rules of the forum, questions should not be confined to solving or completing student assignments. Please clarify what you have done yourself and what did not work out. - Sleeping Owl
  • What's the problem? The direct solution (iterating over the numbers, counting for each dividers and their sum, remembering the current largest in a variable) is not appropriate? - VladD pm
  • five
    I do not remember how in pascal, and on a python in three lines N = 19 # the given number is z = max ([(sum ([x for x in xrange (1, t + 1) if t% x == 0]), t) for t in xrange (1, N + 1)]) print ("max =% d, n =% d"% z) translate :) - KoVadim
  • one
    in my example, z is stupid (such a list, in this case of two numbers). max, if given an array of tuples, finds the maximum in the first element tupla. And it is the sum of dividers. The second element is the number itself. > In your code, if I'm not mistaken, there is a maximum, and not the value on which it is reached. Therefore, in my code there is both the maximum value and the number at which it is reached. See the latest print. - KoVadim pm
  • four
    I vote for the closure of this issue as not relevant topic, because it is a request to do a training task for the user - awesoon

2 answers 2

If you first estimate where the divisors of any number are in general, you will find that you should look for dividers of the number N only in the range from 0 to N / 2, plus the divisor N. Let me explain with the example of the number 36:

Делители: 1,2,3,4,6,9,12,18 ... и 36. Как видите, все неизвестные делители находятся лишь в первой половине числа, т.е от 1 до N/2 плюс само N, т.е 36. 

It is obvious.

The next point:

 Раз мы ищем сумму всех делителей числа, то по логике вещей, те числа, что ближе к N будут иметь сумму делителей больше, чем те, что дальше. Но! Это не всегда так, поэтому в используемом ниже алгоритме диапазон поделен лишь поровну, чего в общем-то достаточно. 

I will offer this algorithm:

  int N = 20000; int dp_summ = 0, dp=0, ch = 0; for(int i=N/2;i<=N;i++) { int ost = (i%10); if(dp>2 && (ost==1 || ost==3 || ost==7 || ost == 9)) continue; int curr = 0, curr_dp=0; for(int j=1;j<=i/2;j++) if(i%j==0) {curr+=j; curr_dp++;} curr+=i;curr_dp++; if(curr>dp_summ) {dp_summ=curr; dp=curr_dp; ch = i;} } printf("Digit is %i have sum of dividers = %i, diveders = %i\n",ch,dp_summ,dp); 

Also in the algorithm, you can implement any other algorithm to accelerate. For example, Luc's algorithm for checking the numbers for simplicity. But let it remain to you as an independent work =)

The task is your average level, interesting even a little) Here I myself am interested to find the most correct solution. All valid criticism of the above algorithm is welcome.

    Recently he helped a friend to optimize the algorithm for calculating the amount of dividers, so he only slightly changed the workpiece. Delphi code, but I think you will not be difficult to remake a pascal.

     function TForm1.FindMaxDel(x: integer): integer; // х - диапазон var n, n2, s, i, maxDel:integer; del: integer; begin MaxDel:= 0; //максимальная сумма делителей for n := 1 to x do // пробегаем весь диапазон begin s:= 0; // тут обнуляем сумму делителей // Тут начинается магия if n mod 2 = 0 then del:= 2 else if n mod 3 = 0 then del:= 3 else if n mod 5 = 0 then del:= 5 else if n mod 7 = 0 then del:= 7 else del:= 0; // тут заканчивается магия // дальше идет расчет суммы делителей if del = 0 then inc(s) else for i:=1 to (n div del) do if n mod i =0 then S:=i+s; s:= s + n; // Если сумма делителей больше текущей, то отмечаем её if s > MaxDel then begin MaxDel:= s; Result:= n; end; end; end; 
    • And why do you go to x? You can shorten the run time, if after finding a simple divider, immediately divide x into it. So you will find a lot of simple dividers, and having it in your hands, the amount is easy to calculate. - VladD
    • > To find from the range from 1 to N this range must be completely passed, in "for n: = 1 to x do" x - this is the user-defined range within which the number will be searched. If you looked at the code further, you would see magic, which reduces the search range of divisor sums for a particular number: if n mod 2 = 0 then del: = 2 ... for i: = 1 to (n div del) do .. . - teanYCH
    • @teanS: Well, it only works for small dividers. And for the number 11*13*17*19*23*29*31*37 your algorithm will take you long enough. - VladD