Задание 25

Делители числа

25_7:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [126849; 126871], числа, имеющие ровно 4 различных делителя.
Выведите эти четыре делителя для каждого найденного числа в порядке возрастания.


    ✎ Решение (неоптимизированный вариант, метод полного перебора):

    PascalABC.net (LINQ):

    1
2
3
4
5
6

    ##
uses school;
var ar:=(126849..126871)
 .where(n->n.DivisorsCount=4)
 .Select(n->n.divisors) 
 .printlines;
    PascalABC.net (с элементами функционального программирования):

    1
2
3
4

    ##
uses school;  
for var i:=126849 to 126871 do   
   if i.DivisorsCount=4 then Println(i.divisors);
    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

    begin
  var divCount := 4;
  for var n := 126849 to 126871 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to n do
      if n mod d = 0 then begin
        divs.Add(d);      
        if divs.Count > divCount then break;
      end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      Println(divs);
    end;
  end;
end.
    Python (1 вариант, Генерация списка делителей):
    Общая идея:

  • Для каждого числа указанного диапазона генерируем список делителей.
  • Если длина списка равна четырем, выводим его.
    • 1
2
3
4

    for n in range(126849, 126871+1):
  divs = [d for d in range(1, n+1) if n % d == 0] 
  if len(divs) == 4:
    print( *divs )
    Python (2 вариант):

    1
2
3
4
5
6
7
8

    for n in range(126849,126871+1):
      divs = [] # чистим список делителей
      for d in range(1,n+1): #
        if n % d == 0:
          divs = divs + [d] # добавляем делитель в список
          if len(divs) > 4: break
      if len(divs) == 4:
        print(*divs)
    С++:

    1

     

    ✎ Решение (оптимизированный вариант):

  • Будем использовать оптимизированный вариант программы, подходящий для «медленных» компьютеров. Для этого перебор делителей для числа n будем выполнять от 2 до √n, округлив его до ближайшего целого числа (не включая точный квадратный корень, если он существует):
    • вместо диапазона делителей [1; число]
использовать диапазон [1; округл(√n)]
  • При переборе делителей будем определять: если делитель – это точный квадратный корень(n), то в список делителей добавлять будем только сам делитель, если нет – то добавляем пару делителей (делитель и n // делитель):
    • Пример:
число 8 = 2 * 4
Достаточно рассмотреть цикл от 2 до округл(√8) (=2)
если 8 делится на 2 и 8/2 не равно 2, то делители: 2 и 4 (8/2)
    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    begin
  var divCount := 4;
  for var n := 126849 to 126871 do
  begin
    var divs := new List<integer>;
    var d := 1;
    while d * d <= n do  // можно цикл for var d := 1 to round(sqrt(n)) do
    begin
      if n mod d = 0 then begin
        divs.Add(d);      
        if d * d <> n then 
          divs.Add(n div d);
        if divs.Count > divCount then break;
      end;
      d := d+1;
    end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      Println(divs);
    end;
  end;
end.
    Python:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    # import math # для квадратного корня числа (sqrt)
divCount = 4  # нужное количество делителей
for n in range(126849,126871 + 1):
  divs = [] # чистим список делителей
  d = 1
  #  вместо while можно цикл for d in range(1,round(math.sqrt(n))):
  while d*d <= n: # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
      if d != n//d: # если делитель - не точный квадратный корень n
        divs.append(n//d)
      if len(divs) > divCount: break
    d+=1
  if len(divs) == divCount:
    divs.sort()
    print(divs)
    С++:

    1

     

Ответ:

1 3 42283 126849
1 47 2699 126853
1 5 25373 126865
1 293 433 126869

25_8:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [164700; 164752], числа, имеющие ровно 6 различных делителей.
Выведите эти делители для каждого найденного числа в порядке возрастания.


    ✎ Решение (неоптимизированный вариант):

    PascalABC.net (LINQ):

    1
2
3
4
5

    ##
uses school; 
(164700..164752).Where(x->x.divisors.count=6)
  .Select(x->x.divisors.Order)
  .printlines
    PascalABC.net (с элементами функционального программирования):

    1
2
3

    uses school;  
  for var i:=164700 to 164752 do   
      if i.DivisorsCount=6 then Println(n);

    ✎ Решение (оптимизированный вариант):

    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

    begin
  var divCount := 6;
  for var n := 164700 to 164752 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to round(sqrt(n)) do
      if n mod d = 0 then begin
        divs.Add(d);      
        if d * d <> n then 
          divs.Add(n div d);
        if divs.Count > divCount then break;
      end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      Println(divs);
    end;
  end;
end.
    Python (вариант 1, генерация списка делителей):

    for n in range(164700, 164752+1):
    divs = [d for d in range(1, n+1) if n % d == 0] 
    if len(divs) == 6:
        print( *divs )
    Python (вариант 2):

    1
2
3
4
5
6
7
8
9
10
11
12
13

    import math # для квадратного корня sqrt
divCount = 6  # нужное количество делителей
for n in range(164700, 164752 + 1):
  divs = [] # чистим список делителей
  for d in range(1,round(math.sqrt(n))): # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
      if d != n//d:
        divs.append(n//d)
      if len(divs) > divCount: break
  if len(divs) == divCount:
    divs.sort()
    print(divs)
    С++:

    1

     

Ответ:

1 2 4 41177 82354 164708
1 3 9 18301 54903 164709
1 2 4 41179 82358 164716
1 2 4 41183 82366 164732

25_9:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [190201; 190230], числа, имеющие ровно 4 различных делителя.
Выведите эти четыре делителя для каждого найденного числа в порядке убывания.


    ✎ Решение (неоптимизированный вариант, метод полного перебора):

    PascalABC.net (LINQ):

    1
2
3
4
5

    ##
uses school; 
(190201..190230).Where(x->x.divisors.count=4)
  .Select(x->x.divisors.OrderDescending)
  .printlines
    PascalABC.net (с элементами функционального программирования):

    1
2
3
4
5

    ##
uses school;  
for var i:=190201 to 190230 do 
   if i.DivisorsCount=4 then 
      i.Divisors.SortedDescending.Println;
    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    begin
  var divs := new integer[4];
  for var n := 190201 to 190230 do
  begin
    var i := 0; // для индекса массива
    for var d := 1 to n do
    begin
      if n mod d = 0 then 
      begin
        if i < 4 then
          divs[i] := d;
        inc(i);
      end;
      if i > 4 then 
        break; 
    end;
    if i = 4 then begin
      println(divs.Reverse())
    end;
  end;
end.
    Python:

    1
2
3
4
5
6
7
8
9

    for n in range(190201,190230+1):
      divs = [] # чистим список делителей
      for d in range(1,n+1): #
        if n % d == 0:
          divs = divs + [d] # добавляем делитель в список
          if len(divs) > 4: break
      if len(divs) == 4:
        divs.reverse()
        print(*divs)
    С++:

    1

     

    ✎ Решение (оптимизированный вариант):

    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    begin
  var divCount := 4;
  for var n := 190201 to 190230 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to round(sqrt(n)) do
      if n mod d = 0 then begin
        divs.Add(d);      
        if d * d <> n then 
          divs.Add(n div d);
        if divs.Count > divCount then break;
      end;
    if divs.Count = divCount then
    begin
      divs.Sort();
      divs.Reverse();
      Println(divs);
    end;
  end;
end.
    Python (вариант 1, генерация списка делителей):

    for n in range(190201, 190230+1):
    divs = [d for d in range(1, n+1) if n % d == 0] 
    if len(divs) == 4:
        divs.reverse() # реверсируем (по убыванию)
        print( *divs )
    Python (вариант 2):

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    import math # для квадратного корня sqrt
divCount = 4  # нужное количество делителей
for n in range(190201, 190230 + 1):
  divs = [] # чистим список делителей
  for d in range(1,round(math.sqrt(n))): # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
      if d != n//d:
        divs.append(n//d)
      if len(divs) > divCount: break
  if len(divs) == divCount:
    divs.sort()
    divs.reverse()
    print(divs)
    С++:

    1

     

Ответ:

190201 17291 11 1
190202 95101 2 1
190214 95107 2 1
190219 853 223 1
190222 95111 2 1
190223 17293 11 1
190227 63409 3 1
190229 14633 13 1


25_10:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [190201; 190280], числа, имеющие ровно 4 различных ЧЁТНЫХ делителя.
Выведите эти четыре делителя для каждого найденного числа в порядке убывания.


    ✎ Решение (неоптимизированный вариант, метод полного перебора):

    PascalABC.net (LINQ):

    1
2
3
4
5
6

    ##
uses school; 
(190201..190280)
  .Where(x->x.Divisors.Where(d->d.divs(2)).Count=4)
  .Select(x->x.divisors.Where(d->d.divs(2)).OrderDescending)
  .printlines
    PascalABC.net (с элементами функционального программирования):

    1
2
3
4
5
6
7
8
9
10

    ##
uses school;  
  for var i:=190201 to 190280 do 
  begin
    var ev:=0;
    for var j:=1 to i.Divisors.Count-1 do
      if i.Divisors[j].IsEven then ev+=1; 
    if ev=4 then 
      i.Divisors.Where(t -> t.IsEven).SortedDescending.Println;
  end;
    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    begin
  var divs := new integer[4];
  for var n := 190201 to 190280 do
  begin
    var i := 0; // для индекса массива
    for var d := 1 to n do
    begin
      if (n mod d = 0) and (d mod 2 = 0) then 
      begin
        if i < 4 then
          divs[i] := d;
        inc(i);
      end;
      if i > 4 then 
        break; 
    end;
    if i = 4 then begin
      println(divs.Reverse())
    end;
  end;
end.
    Python (вариант 1, генерация списка делителей):

    for n in range(190201, 190280+1):
    divs = [d for d in range(1, n+1) if n % d == 0 and d % 2 == 0] 
    if len(divs) == 4:
        divs.reverse()
        print( *divs )
    Python (вариант 2):

    1
2
3
4
5
6
7
8
9

    for n in range(190201,190280+1):
      divs = [] # чистим список делителей
      for d in range(1,n+1): #
        if n % d == 0 and d%2==0:
          divs = divs + [d] # добавляем делитель в список
          if len(divs) > 4: break
      if len(divs) == 4:
        divs.reverse()
        print(*divs)
    С++:

    1

     

Ответ:

190226 838 454 2
190234 17294 22 2
190238 2606 146 2
190252 95126 4 2
190258 758 502 2
190274 27182 14 2
190276 95138 4 2

25_11:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [394441; 394505], числа, имеющие максимальное количество различных делителей. Если таких чисел несколько, то найдите минимальное из них.
Выведите количество делителей найденного числа и два наибольших делителя в порядке убывания.

✍ Решение:

    ✎ Решение (неоптимизированный вариант, метод полного перебора):

    PascalABC.net (LINQ):

    1
2
3
4
5
6
7
8

    ##
uses school; 
var ma:=(394441..394505)
  .Select(x->x.divisors.count).max; // max
(394441..394505)
  .Where(x->x.divisors.count=ma)
  .Select(x->(x.divisors.Count,x,x.divisors[x.Divisors.Count-2]))
  .First.print
    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

    begin
  var max := 0;
  var divsMax := new List<integer>; 
  for var n := 394441 to 394505 do
  begin
    var divs := new List<integer>; 
    for var d := 1 to n do
      if n mod d = 0 then 
        divs.Add(d);      
    if divs.Count > max then 
    begin
      max := divs.Count;
      divsMax := divs;
    end;
  end;
  divsMax.Reverse();
  print(max, divsMax[0], divsMax[1])
end.
    Python (вариант 1, генерация списка делителей):

    maxim=0
divsmax=[]
for n in range(394441, 394505+1):
    divs = [d for d in range(1, n+1) if n % d == 0] 
    if len(divs) > maxim:
        maxim = len(divs)
        divsmax = divs # сохраняем делители для числа с макс кол-вом дел-ей
divsmax.reverse()
print(maxim, divsmax[0], divsmax[1])
    Python (вариант 2):

    1
2
3
4
5
6
7
8
9
10
11
12

    maxim = 0  # нужное количество делителей
divsMax = []
for n in range(394441, 394505 + 1):
  divs = [] # чистим список делителей
  for d in range(1,n+1): # перебор делителей
    if n % d == 0:
      divs.append(d) # добавляем делитель в список
  if len(divs) > maxim: 
    maxim = len(divs)
    divsMax = divs
divsMax.reverse()
print(maxim,divsMax[0],divsMax[1])
    С++:

    1

     

Ответ: 48 394450 197225

Комментарии

Отправить комментарий