Нахождение чисел, которые представляют собой произведение двух различных простых делителей, заканчивающихся на одну и ту же цифру

Question

Сегодня решал задачу по информатике, которая звучит так: Среди целых чисел, принадлежащих числовому отрезку [264871; 322989], найдите числа, которые представляют собой произведение двух различных простых делителей, заканчивающихся на одну и ту же цифру. Запишите в ответе количество таких чисел и их среднее арифметическое. Для среднего арифметического запишите только целую часть числа. Я попытался ее решить и получился у меня вот такой ответ, который оказался неправильным: 2054 293905. В своей программе я попытался сначала определить является ли число делителем, а потом проверить равны ли концы этих делителей, и если счетчики совпадают, то число добавляется в сумму и прибавляется счетчик таких чисел. Правильный ответ к этой задаче: 2182 293612. Возможно он, конечно, не правильный, но скорее всего тут нет ошибки. Я не понимаю откуда взялись еще эти 100 чисел и что я делаю не так. Прошу помочь; вот мой код:

from math import ceil, sqrt
sum = 0
l = 0
for i in range(264871,322990):
    k = 0
    d = 0
for j in range(1,ceil(sqrt(i))):
    if i%j==0:
        k+=2
    if (j%10)==((i/j)%10):
        d+=2
if k==d:
    sum+=i
    l+=1
print(l,sum/l)

Answer 1

Хоть этот ответ и выкладывается через почти два года после вопроса, но сама задача остаётся актуальной, поэтому я выложу код которым решил эту задачу, надеюсь кому нибудь он поможет, а в идеале чтобы даже кто-то его усовершенствовал

import math
def divs(n):
    divs = []
    for i in range(2,int(math.sqrt(n))+1):
        if n%i == 0:
            divs.extend([i,n/i])
    return list(set(divs))
k=0
summ=0
for x in range(264871,322990):
    if len(divs(x))==2:
        for num in divs(x):
            if len(divs(num))==0 and divs(x)[0]%10==divs(x)[1]%10:
                summ+=x
                k+=1
print(summ/k,k/2)

делить кол-во чисел которые мы получаем на 2 нужно из - за того, что мы в цикле дважды заходим в это условие(т.к. у нас два простых делителя), конечно это костыль, но по другому я не придумал

Answer 2

factors разлагает целое в произведение степеней простых. fits выбирает из разложения первый два множителя, проверяет что их степени - единицы, что они кончаются на одну и ту же цифру. main считает количество и среднее:

import math


def factors(n):
    i = 2
    j = n
    j_sqrt = math.isqrt(j)
    while i <= j_sqrt:
        if j % i == 0:
            p = 0
            while j % i == 0:
                j //= i
                p += 1
            yield i, p
            j_sqrt = math.isqrt(j)
        i += 1 if i == 2 else 2
    if j > 1:
        yield j, 1
        

def fits(n):
    it = factors(n)
    p1, e1 = next(it, (0, 2))
    if e1 != 1:
        return False
    p2, e2 = next(it, (0, 2))
    if e2 != 1:
        return False
    return p1 * p2 == n and p1 % 10 == p2 % 10


def main():
    k = 0
    s = 0
    for n in range(264871, 322989 + 1):
        if fits(n):
            k += 1
            s += n

    print(k, s // k)


main()

Примерно треть секунды:

$ time python temp.py
2182 293612

real  0m0.365s
user  0m0.356s
sys   0m0.004s

Answer 3

Подняли ветку - не смог удержаться ;) от альтернативного подхода (~0.02 сек)

Вместо проверки чисел в диапазоне проверяем произведения пар простых на попадание в диапазон. (Можно ещё простые на 4 списка разделить и проверять только внутри каждого).

Простые числа в парах могут только нечетные, т.к. к двойке пары нет, и поэтому решето Эратосфена проходит только по нечётным числам,и используемый массив половинной длины. Шаг по индексам в такой реализации тоже получается равным обрабатываемому простому числу (3#-5--7-9*-11-13-15*...). Наибольшее число может быть парным тройке, поэтому верхний предел для поиска простых чисел hi//3. Для заданного интервала длина списка простых получается около 10000

Запускаем пару индексов левый l и правый r по списку простых чисел. Ищем подходящий правый для текущего левого индекса, потом проходим от него вниз, проверяя пары, пока не дойдём до нижнего предела. Сдвигаем левый индекс и всё повторяем, пока индексы не сойдутся.

import time

def eratospheneodd(nmax):
    candidates = [(2*i+1) for i in range((nmax+1)//2)]
    candidates[0] = 0
    for i in range(1, len(candidates)):
        if candidates[i]:
            for j in range(i+candidates[i], (nmax+1)//2, candidates[i]):
                candidates[j]=0
    return [x for x in candidates if x]

t = time.time()
lo = 264871
hi = 322989
primes = eratospheneodd(hi//3)
cnt, summ = 0, 0

l, r  = 0, len(primes) - 1
while l < r:
    while primes[l]*primes[r] > hi:
        r-=1
    rr = r
    while primes[l]*primes[rr] >= lo and rr>l:
        if primes[l]%10==primes[rr]%10:
            cnt += 1
            summ += primes[l]*primes[rr]
        rr-=1
    l+=1
print(cnt, summ//cnt)
print(time.time()-t)

БЛОГ НА HUSL

Нахождение чисел, которые представляют собой произведение двух различных простых делителей, заканчивающихся на одну и ту же цифру

Ответы (3 шт):