Форум » Обработка целых чисел » Задание 25 № 2611 » Ответить
Задание 25 № 2611
JoBush: Рассматриваются целые числа, принадлежащих числовому отрезку [236228; 305283], которые представляют собой произведение трёх различных простых делителей. В ответе запишите количество таких чисел и их среднее арифметическое (только целую часть числа). Вот мое решение: [pre2]from itertools import * def prosto(t): for l in range(2,int(t**0.5)+1): if t % l == 0: return False return True c = 0 m = 0 for i in range(236228, 305283+1): a = [] for j in range(2,int(i**0.5)+1): if i % j == 0 and prosto(j): a.append(j) if i//j != j and prosto(i//j): a.append(i//j) if len(a)<3: continue s = list(map(str,a)) perm = permutations(s,r=3) ss = [list(map(int,j)) for j in perm] for j in ss: if j[0] * j[1] * j[2] == i: c+=1 m+=i break print(c, m/c) [/pre2] Мой ответ: 2840 270327 В ответе должно быть: 14216 270732 Что не так? Помогите, пожалуйста
Ответов - 4
Ж: [pre2] from itertools import * def g(n): #решето эратосфена для отбора простых чисел l=[]; r=set() for i in range(2,n+1): if i not in r: l.append(i) r.update(range(i**2,n+1,i)) return l res=g(50880) de=lambda n: list(set(chain(*[(a,n//a) for a in range(1,ceil(n**0.5)) if n%a==0 ]))) #список делителей числа n l=[] for n in range(236228,305283+1): sp=de(n) if len(sp)==8 and len([c for c in sp if c in res])==3: (если раскладывается в произведение 3-х простых множителей, то число его делителей равно 8, есть формула числа делителей, связанная с разложением на простые множители и со степенями этих множителей) l.append(n) print(len(l), sum(l)//len(l)) [/pre2] ответ 14216 270732
JoBush: Ж пишет: res=g(50880) Почему вы берете 50880?
JoBush: Ж пишет: есть формула числа делителей, связанная с разложением на простые множители и со степенями этих множителей Можете, пожалуйста, написать эту формулу или сказать название.
Ж: n=p1^k1 * p2^k2 * p3^k3 * ...pm^km --> количество делителей = (k1+1)*(k2+1)*...(km+1) Пример 72=2^3 * 3^2 72 делится на [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72] количество делителей = (3+1) * (2+1) = 12 50880 = 305283/2/3 (это оценка сверху 3-го простого делителя, чтобы список простых был поменьше). Но это необязательно, можно написать res = g(305283) - считаться будет в 3 раза дольше (сейчас 20 с, иначе 60 с - терпимо, можно сделать оптимальней, но и минута - не проблема подождать)
полная версия страницы