25 - Обработка целочисленных данных. Поиск делителей

Источники:

сайт Полякова (https://kpolyakov.spb.ru/)

демонстрационная версия станции КЕГЭ (https://kompege.ru/)

1) (№ 3657) Среди целых чисел, принадлежащих числовому отрезку [1000000; 1300000], найдите числа, у которых все цифры меньше тройки, а сумма цифр кратна десяти. Среди всех таких чисел необходимо отобрать каждое десятое (10-е, 20-е, 30-е и т.д.). Расположите найденные числа в порядке возрастания, справа от каждого числа укажите количество его собственных делителей (меньших, чем само число).

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return list(sorted(d))

n=0

for i in range(1000000,1300000+1):

i=str(i)

s=0

if max(i)<'3':

s=sum(map(int,i))

if s%10==0:

n+=1

if n%10==0:print(i,len(div(int(i)))-1)

Ответ:

1112221 3

1122220 23

1212112 39

1221121 7

1222210 31

2) (№3441 / №787) Для интервала [33333;55555] найдите числа, которые кратны сумме своих простых делителей. В качестве ответа приведите числа, для которых сумма простых делителей больше 250, – сначала найденное число, затем сумму его простых делителей. Примечание: само число в качестве делителя не учитывается.

Решение

Вариант 1

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return list(sorted(d))

a,b=33333,55555

m=[1]*(b+1)

m[0]=m[1]=0

for i in range(2,int(b**0.5)):

if m[i]:

for k in range(i*i,b+1,i):m[k]=0

for i in range(a,b+1):

s=0

for d in div(i)[:-1]:

if m[d]: s+=d

if s>250 and i%s==0:

print(i,s)

Вариант 2

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:d.add(i);d.add(x//i)

return sorted(list(d))

def pr(x):

if x<2: return 0

if x%2==0: return x==2

d=3

while d*d<x and x%d!=0:d+=2

return d*d>=x

for x in range(33333,55555+1):

d=div(x)[1:-1]

s=0

for c in d:

if pr(c):s+=c

if s>250 and x%s==0: print(x,s)

Ответ:

38086 278

44998 302

53332 268

3)(№3440) Для интервала [33333;55555] найти все простые числа, сумма цифр которых больше 35. Запишите найденные числа в порядке возрастания, справа от каждого – сумму его цифр.

Решение

a,b=33333,55555

m=[1]*(b+1)

p=[];m[0]=m[1]=0

for i in range(2,int(b**0.5)):

if m[i]==1:

for k in range(i*i,b+1,i):m[k]=0

for i in range(a,b+1):

if m[i]: p.append(i)

for i in p:

s=sum(map(int,str(i)))

if s>35:

print(i,s)

Ответ:

39799 37

39979 37

39989 38

48799 37

48889 37

48989 38

49789 37

49999 40

4) (№3437) Рассматривается множество целых чисел, принадлежащих числовому отрезку [862346; 1056242]. Найдите числа, нетривиальные делители которых образуют арифметическую прогрессию с разностью d = 100. В ответе для каждого такого числа (в порядке возрастания) запишите сначала само число, а потом – его максимальный нетривиальный делитель.

Решение

n=1056242

m=[1]*(n+1)

for i in range(2,int(n**0.5)):

if m[i]:

for k in range(i*i,n+1,i):m[k]=0

for i in range(862346,1056242):

d=(10000+4*i)**0.5

if d>0 and d==int(d):

x=(100+d)/2

if x==int(x):

x=int(x)

if m[x]*m[x-100]==1:

print(i,x)

Ответ:

867989 983

936461 1019

5) (№3436) Рассматривается множество целых чисел, принадлежащих числовому отрезку [834567; 1143210]. Найдите числа, нетривиальные делители которых образуют арифметическую прогрессию с разностью d = 2. В ответе для каждого такого числа (в порядке возрастания) запишите сначала само число, а потом – его максимальный нетривиальный делитель.

Решение

r,n=2,1143210

m=[1]*(n+1)

m[0],m[1]=0,0

for i in range(int(n**0.5)+1):

if m[i]:

for k in range(i*i,n+1,i):m[k]=0

for i in range(834567, n+1):

d=(r*r+4*i)**0.5

if d>0 and d==int(d):

x=(r+d)/2

if x==int(x):

x=int(x)

if m[x]*m[x-r]==1:

print(i,x)

Ответ:

1040399 1021

1065023 1033

1102499 1051

1127843 1063

6) (№3435) Рассматривается множество целых чисел, принадлежащих числовому отрезку [854321; 1087654]. Найдите числа, нетривиальные делители которых образуют арифметическую прогрессию с разностью d = 10. В ответе для каждого такого числа (в порядке возрастания) запишите сначала само число, а потом – его минимальный нетривиальный делитель.

Решение

r=10

n=1087654

m=[1]*(n+1)

for i in range(2,int(n**0.5)):

if m[i]==1:

for k in range(i*i,n+1,i):m[k]=0

for i in range(854321,1087654):

d=(r*r+4*i)**0.5

if d>0 and d==int(d):

x=(r+d)/2

if x==int(x):

x=int(x)

if m[x]*m[x-r]==1:

print(i,x-10)

Ответ:

887339 937

944759 967

1028171 1009

1052651 1021

7) (№3161) Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 18 получим: 18 = 18*1 = 9*2 = 6*3, множество разностей содержит числа 17, 7 и 3. Подходящей будем называть пару сомножителей, разность между которыми не превышает 120. Найдите все натуральные числа, принадлежащие отрезку [2000000; 3000000], у которых есть не менее трёх подходящих пар сомножителей. В ответе перечислите найденные числа в порядке возрастания, справа от каждого запишите наибольший из всех сомножителей, образующих подходящие пары.

Решение

for i in range(2000000,3000000):

k=0

g=int(i**0.5)

for d in range(g,g-100,-1):

if i%d==0:

r=i//d-d

if r<=120:

k+=1

m=i//d

else: break

if k>2:

print(i,m)

Ответ:

2053440 1488

2098080 1504

2328480 1584

2620800 1680

2638944 1683

2692800 1700

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

Решение

n=126871

m=[1]*(n+1)

m[0],m[1]=0,0

p=[]

for i in range(2,int(n**0.5)):

if m[i]:

for k in range(i*i,n+1,i):m[k]=0

for i in range(126849,126871+1):

for d in range(2,int(i**0.5)):

if i%d==0:

if m[d]==1 and m[i//d]==1:

print(i//d,i)

break

Ответ:

42283 126849

2699 126853

25373 126865

433 126869

9) (№2912) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [157898; 157990], числа, имеющие ровно 6 различных делителей. Выведите для каждого найденного числа два его наибольших делителя, не равных самому числу, в порядке убывания.

Решение

Вариант 1

n=157990

m=[1]*(n+1)

p=[]

for i in range(2,int(n**0.5)):

if m[i]==1:

for k in range(i*i,n+1,i):m[k]=0

for i in range(2,n+1):

if m[i]==1: p.append(i)

for i in range(157898,157990+1):

dd=[]

for d in p:

dk=0

while i%d==0:

dd.append(d)

i//=d

if len(dd)>3:

break

if len(dd)==3 and max(dd)>min(dd):

if dd[0]==dd[1]: print (dd[0]*dd[2],dd[2])

elif dd[1]==dd[2]: print(dd[1]*dd[2],dd[2]*dd[0])

Вариант 2

for i in range(157898,157990):

k=0

m1=0

m2=0

for d in range(2,i//2+1):

if i%d==0:

k+=1

m1=m2

m2=d

if k>4: break

if k==4: print(m2,m1)

Ответ:

78961 562

31585 6317

52653 17551

10) (№ 2903 Б.С.Михлин) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [573213; 575340] число с минимальной суммой делителей, имеющее ровно четыре делителя. Для найденного числа выведите сумму делителей, и количество делителей.

Решение

n=575340

m=[1]*(n+1)

p=[]

for i in range(2,int(n**0.5)):

if m[i]:

for k in range(i*i,n+1,i):m[k]=0

mm=0

for i in range(573213,575340+1):

for d in range(2,int(i**0.5)):

if i%d==0:

if m[d]==1 and m[i//d]==1:

if mm>i+d+i//d or mm==0:

mm=i+d+i//d

break

print(mm+1,4)

Ответ: 574992 4

11) (№2902) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2943444; 2943529], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.

Решение

Вариант 1

n=2943529

m=[1]*(n+1)

p=[]

for i in range(2,int(n**0.5)):

if m[i]==1:

for k in range(i*i,n+1,i):m[k]=0

for i in range(2,n+1):

if m[i]==1: p.append(i)

k=0

for i in p:

if i>=2943444:

k+=1

print(k,i)

Вариант 2

n=2943529

m=[1]*(n+1)

p=[]

for i in range(2,int(n**0.5)):

if m[i]==1:

for k in range(i*i,n+1,i):m[k]=0

k=0

for i in range(2943444,2943529+1):

if m[i]==1:

k+=1

print(k,i)

Ответ:

1 2943467

2 2943491

3 2943503

4 2943527

12) (№2879) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2532000; 2532160], простые числа. Найдите все простые числа, но выведите на экран только каждое третье простое число (то есть числа с порядковыми номерами 1, 4, 7, 10, …). Вывод осуществите в порядке возрастания, слева от каждого числа выведите его собственный порядковый номер среди всех простых чисел.

Решение

n=2532160

m=[1]*(n+1)

p=[]

for i in range(2,int(n**0.5)):

if m[i]==1:

for k in range(i*i,n+1,i):m[k]=0

k=0

for i in range(2532000,2532160+1):

if m[i]==1:

k+=1

if k%3==1: print(k,i)

Ответ:

1 2532007

4 2532083

7 2532113

10 2532157

13) (№ 3779) Найдите все натуральные числа, принадлежащие отрезку [78 000 000; 85 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа, справа от каждого числа запишите его наибольший нечётный делитель.

Решение

def pint(n):

if n<2: return n>1

elif n % 2 == 0:

return n == 2

d = 3

while d * d <= n and n % d != 0:

d += 2

return d * d > n

for x in range(78000000,85000000+1):

i=x

while i%2==0: i//=2

d=i**0.25

if d==int(d) and pint(int(d)):

print(x,i)

Ответ:

78074896 4879681

78675968 2401

80604484 20151121

81920000 625

84934656 81

14) (№ 3982) Найдите все натуральные числа, N, принадлежащие отрезку [100 000 000; 300 000 000], которые можно представить в виде N = 2m•7n, где m – нечётное число, n – чётное число. В ответе запишите все найденные числа в порядке возрастания, а справа от каждого числа – сумму m+n.

Решение

Вариант 1

a = 1

m=[]

while a < 30:

b = 0

while b < 12:

if ((2**a)*(7**b)) in range(100000000, 300000001):

m.append(str((2**a)*(7**b))+' '+str(a+b))

b += 2

a += 2

m=sorted(m)

for i in range(len(m)):

print(m[i])

Вариант 2

def st(x,y):

k=1

while y**k<=x: k+=1

return k

a,b=100000000,300000000

m=[]

for s2 in range(1,st(b,2),2):

for s7 in range(0,st(b,7),2):

p=2**s2*7**s7

if a<=p<=b:

m.append(str(p)+' '+str(s2+s7))

elif p>b:break

for i in sorted(m):print(i)

Ответ:

102760448 23

134217728 27

184473632 13

240945152 17

15) (№ 3932) Рассматриваются возрастающие последовательности из 5 идущих подряд чисел, больших 700000, такие, что количество делителей каждого следующего числа превосходит количество делителей предыдущего числа. Найдите такую последовательность, которая начинается с наименьшего возможного числа. Для каждого числа из этой последовательности запишите сначала само число, а затем количество его натуральных делителей.

Решение

def kd(n):

k=2

n1=n**0.5

for d in range(2,int(n1)+1):

if n%d==0:k+=2

if n1 == int(n1) : k-=1

return(k)

a=[]

b=[]

for i in range(5):

a.append(700001+i)

b.append(kd(a[i]))

fl=0

while fl==0:

fl=1

for i in range(4):

if b[i]>=b[i+1]: fl=0;break

if fl==1:

for k in range(5):

print (a[k],b[k])

break

else:

a=a[1:]

b=b[1:]

a.append(a[-1]+1)

b.append(kd(a[-1]))

Ответ:

702122 4

702123 8

702124 12

702125 16

702126 24

16) (№ 3927 А. Богданов) Найдите наименьшее натуральное число, которое имеет ровно 512 делителей. В ответе запишите сначала само число и затем его наибольший простой делитель. Подсказка: используйте основную теорему арифметики.

Решение

Вариант 1

a=[23,19,17,13,11,7,5,3,2]

s=[]

mi=23**512

for i in range(10):

s.append(2**i-1)

k=[0]*9

for k[0] in range(2):

for k[1] in range(3):

for k[2] in range(4):

for k[3] in range(5):

for k[4] in range(6):

for k[5] in range(7):

for k[6] in range(8):

for k[7] in range(9):

for k[8] in range(10):

p=1

for i in range(9):

p*=(s[k[i]]+1)

if p==512:

x=1

for i in range(9):

x*=a[i]**s[k[i]]

if x<mi:

mi=x

km=k[:]

for i in range(9):

if km[i]>0:

ma=a[i]

break

print(mi,ma)

Вариант 2

Ответ: 17297280 13

17) (№ 2850) Рассматриваются целые числа, принадлежащих числовому отрезку [356738; 404321], которые представляют собой произведение двух различных простых делителей. В ответе запишите количество таких чисел и такое из них, простые делители которого отличаются друг от друга больше всего.

Решение

Вариант 1 (t = 1.61 c.)

n=404321+1

ma=0

k=0

# решето Эратосфена

m=[1]*n

for i in range(2,int(n**0.5)+1):

for d in range(i*i,n,i): m[d]=0

for i in range(356738,n):

for d in range(2,int(i**0.5)+1):

if m[d]==1 and i%d==0:

if m[i//d]==1 and d!=i//d:

k+=1

if ma <= i//d-d:

ma=i//d-d

mai=i

break

print(k,mai)

Вариант 2 (t = 8.84 c.)

def div(x):

d=set()

for i in range(2,int(x**0.5)+1):

if x%i==0 and len(d)<4: d.add(i);d.add(x//i)

return sorted(list(d))

def p(x):

if x%2==0: return x==2

d=3

while x%d!=0 and d*d<=x: d+=2

return d*d>x

r=0;

k=0

for x in range(356738,404321):

d=div(x)

if len(d)==2 and p(d[1]):

k+=1

if r<d[1]-d[0]: r=d[1]-d[0];maxc=x

print(k,maxc)

Ответ: 10013 404258

18) (№ 2841) Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [106732567; 152673836] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

Решение

Вариант 1 (медленный)

for i in range(106732567, 152673836+1):

md=[]

if int(i**0.5)==i**0.5:

for d in range(2, int(i**0.5)+1):

if i%d==0:

md.append(d)

if i//d not in md:

md.append(i//d)

if len(md)>3:

break

if len(md)==3:

md.sort()

print(i, md[-1])

Вариант 2 (быстрый)

n=int((152673836)**0.25+1)

# Решето Эратосфена

m=[1]*n

for i in range(2,n):

for d in range(i*i,n,i):m[d]=0

for i in range(int(106732567**0.25)-1,n):

if m[i]==1 and 106732567<=i**4<=152673836:

print(i**4,i**3)

Ответ:

112550881 1092727

131079601 1225043

141158161 1295029

19) (№ 2887) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [5408238; 5408389], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.

Решение

Вариант 1

n=5408389+1

m=[1]*n

for i in range(2,n):

for d in range(i*i,n,i):m[d]=0

n=0

for i in range(5408238,5408389+1):

if m[i]==1:

n+=1

print(n,i)

Вариант 2

def pint(n):

if n%2==0: return n==2

d=3

while d*d<=n and n%d!=0:d+=2

return d*d>n

n=0

for i in range(5408238,5408389+1):

if pint(i):

n+=1

print(n,i)

Ответ:

1 5408309

2 5408311

3 5408323

4 5408341

5 5408357

6 5408383

7 5408387

20) (№ 2615) Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Найдите все натуральные числа, принадлежащие отрезку [525784203; 728943762] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе два числа: само число и его наибольший нетривиальный делитель. Найденные числа расположите в порядке возрастания.

Решение

n=int((728943762)**0.25+1)

# Решето Эратосфена

m=[1]*n

for i in range(2,n):

for d in range(i*i,n,i):m[d]=0

print(m[157])

for i in range(int(525784203**0.25)-1,n):

if m[i]==1 and 525784203<=i**4<=728943762:

print(i**4,i**3)

Ответ:

607573201 3869893

705911761 4330747

21) (№ 2861 К.Амеличев) Среди целых чисел, принадлежащих числовому отрезку [3594; 21891], найдите числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Ответом будет максимум среди найденных чисел.

Решение

n=21891+1

k=0

# решето Эратосфена

m=[1]*n

for i in range(2,int(n**0.5)+1):

for d in range(i*i,n,i): m[d]=0

for i in range(3594,n):

for d in range(2,int(i**0.5)+1):

if m[d]==1 and i%d==0:

if m[i//d]==1 and d!=i//d:

mai=i

break

print(mai)

Ответ: 21891

22) (№ 2593 К.Амеличев) Среди целых чисел, принадлежащих числовому отрезку [2945; 18294], найдите числа, не делящиеся на вторую степень какого-либо числа, кроме единицы. Ответом будет сумма цифр найденных чисел.

Решение

n=18294+1

s=0

m=[1]*n

for i in range(2,int(n**0.5)+1):

for d in range(i*i,n,i):m[d]=0

for i in range(2945,n):

fl=1

for d in range(2,int(i**0.5)+1):

if m[d]==1 and i%(d**2)==0: fl=0;break

if fl==1:

for c in str(i):s+=int(c)

print(s)

Ответ: 177084

23) (№2885) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [125873; 136762], числа, имеющие ровно 5 различных делителей. Выведите количество таких чисел и наибольшее их них.

Решение

n=int((136762)**0.25+1)

m=[1]*n

for i in range(2,n):

for d in range(i*i,n,i):m[d]=0

k=0

for i in range(int(125873**0.25)-1,n):

if m[i]==1 and 125873<=i**4<=136762:

ma=i**4

k+=1

print(k,ma)

Ответ: 1 130321

24) (№ 2612) Рассматриваются целые числа, принадлежащих числовому отрезку [536792; 604298], которые представляют собой произведение трёх различных простых делителей, оканчивающихся на одну и ту же цифру. В ответе запишите количество таких чисел и такое из них, для которого разность наибольшего и наименьшего простых делителей максимальна.

Решение

Вариант 1 (время работы программы 0.16 с.)

a,b=536792,604298

m=[1]*(b//2+1)

for i in range(2,int(len(m)**0.5)+1):

if m[i]:

for d in range(i*i,len(m),i): m[d]=0

k,ma=0,0

for i1 in range(3,int(len(m)**(1/3))+1,2):

if m[i1]:

if i1**3>b:break

for i2 in range(i1+10,len(m),10):

if m[i2]:

if i1*i2**2>b:break

for i3 in range(i2+10,len(m),10):

if m[i3]:

x=i1*i2*i3

if a<=x<=b:

k+=1

if i3-i1>ma:

ma=i3-i1

xma=x

elif x>b: break

print(k,xma)

Вариант 2 (время работы программы 7.18 с.)

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:

d.add(i)

d.add(x//i)

return list(sorted(d))

a,b=536792,604298

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for d in range(i*i,b+1,i): m[d]=0

k,maxr=0,0

for i in range(a+1,b+1,2):

d=div(i)

dp=[]

for c in d:

if m[c]: dp.append(c)

if len(dp)==3 and len(d)==8 and dp[0]%10==dp[1]%10==dp[2]%10:

k+=1

if maxr<=dp[2]-dp[0]:

maxr=dp[2]-dp[0]

maxc=i

print(k,maxc)

Ответ: 365 604227

25) (№ 3931 Е.Джобс) Найдите возрастающую последовательность из 5 чисел, начинающуюся с 700000, такую, что каждый следующий элемент – это минимальное число, количество делителей которого превосходит количество делителей предыдущего числа. Для каждого элемента последовательности запишите сначала само число, а затем количество его натуральных делителей.

Решение

Вариант 1 (Время выполнения 3.22 с.)

a=800000

b=False

m=[True]*(a+1)

m[0],m[1]=b,b

for i in range(int(a**0.5)+1):

if m[i]:

for d in range(i*i,a+1,i):m[d]=b

mp=[]

for i in range(a+1):

if m[i]:mp.append(i)

aa=700000

kd,kc=0,0

while kc<5:

k,a,ak=1,aa,int(aa**0.5)+1

for i in mp:

if i>ak:

break

n=0

while a%i==0:

n+=1

a//=i

k*=(n+1)

if kd<k:

kd=k

kc+=1

print(aa,kd)

aa+=1

Вариант 2 (время выполнения 4.71 с.)

def div(x):

d=set()

for i in range(1, int(x**.5)+1):

if x%i==0:

d.add(i)

d.add(x//i)

return d

kd=0

xs=700000

for i in range(5):

for x in range(xs,790000):

d = len(div(x))

if d>kd:

print(x,d)

kd=d

xs=x+1

break

Вариант 3 (время выполнения 6.11 с.)

a=800000

b=False

m=[True]*(a+1)

m[0],m[1]=b,b

for i in range(int(a**0.5)+1):

if m[i]:

for d in range(i*i,a+1,i):m[d]=b

aa=700000

kd,kc=0,0

while kc<5:

k,a=1,aa

for i in range(int(a**0.5)+1):

if m[i]:

n=0

while a%i==0:

n+=1

a//=i

k*=(n+1)

if kd<k:

kd=k

kc+=1

print(aa,kd)

aa+=1

Ответ:

700000 72

700128 144

702000 160

702240 192

720720 240

26) (№ 3980) Найдите все натуральные числа, N, принадлежащие отрезку [100 000 000; 300 000 000], которые можно представить в виде N = 2m•5n, где m – нечётное число, n – чётное число. В ответе запишите все найденные числа в порядке возрастания, а справа от каждого числа – сумму m+n.

Решение

def st(x,y):

k=1

while y**k<=x: k+=1

return k

a,b=100000000,300000000

m=[]

for s2 in range(1,st(b,2),2):

for s5 in range(0,st(b,5),2):

p=2**s2*5**s5

if a<=p<=b:

m.append(str(p)+' '+str(s2+s5))

elif p>b:break

for i in sorted(m):print(i)

Ответ:

128000000 19

134217728 27

200000000 17

209715200 25

27) (№ 4120 А.Кабанов) Обозначим через F целую часть среднего арифметического всех простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение F равным нулю. Напишите программу, которая перебирает целые числа, большие 650000, в порядке возрастания и ищет среди них такие, для которых значение F при делении на 37 даёт в остатке 23. Выведите первые 4 найденных числа в порядке возрастания и справа от каждого числа – соответствующее значение F.

Решение

a,b=650000,700000

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for d in range(i*i,b+1,i): m[d]=0

mp=[]

for i in range(b+1):

if m[i]: mp.append(i)

kc=0

while kc<4:

a+=1

if not(m[a]):

md=[]

for i in mp:

if a%i==0: md.append(i)

sr=sum(md)//len(md)

if sr%37==23:

print(a,sr)

kc+=1

Ответ:

650090 60

650153 282

650155 3945

650208 134

28) (№ 4123 С.Неретин) Пифагоровой тройка назовём тройку чисел (a, b, c), такую что a ≤ b ≤ с и a2 + b2 = c2. Найдите все пифагоровы тройки, в которых все числа находятся в диапазоне [1; 5000]. Запишите в ответе количество подходящих троек, а затем – значение c для тройки, в которой сумма a + b + c максимальна.

Решение

k,maxabc=0,0

for a in range(1,5000-1):

for b in range(a,5000):

c=(a*a+b*b)**0.5

if c==int(c):

k+=1

if maxabc < a+b+c:

maxabc=a+b+c

ck=c

if c>5000: break

print(k,int(ck))

Ответ: 5681 4988

29) (№ 2897) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2358827; 2358891], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.

Решение

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

k=1

for i in range(2358827,2358891+1):

if pint(i):

print(k,i)

k+=1

Ответ: 1 2358827

2 2358841

3 2358859

4 2358877

5 2358887

30) (№ 2562 Демовариант 2021г.) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.

Решение

a=174457

b=174505

# Решето Эратосфена

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for d in range(i*i,b+1,i): m[d]=0

for i in range(a,b+1):

for d in range(int(i**0.5)+1):

if m[d] and i%d==0 and (m[i//d] or i==d**3):

print(d,i//d)

Ответ:

3 58153

7 24923

59 2957

13 13421

149 1171

5 34897

211 827

2 87251

31) (№ 2563) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [3532000; 3532160], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.

Решение

Решение 1

a=3532000

b=3532160

# Решето Эратосфена

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for d in range(i*i,b+1,i): m[d]=0

k=0

for i in range(a,b+1):

if m[i]:

k+=1

print(k,i)

Решение 2

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

a=3532000

b=3532160

k=0

for i in range(a,b+1):

if pint(i):

k+=1

print(k,i)

Ответ:

1 3532007

2 3532019

3 3532021

4 3532033

5 3532049

6 3532091

7 3532103

8 3532121

9 3532147

32) (№ 2564) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [194455; 194500], числа, имеющие ровно 4 различных делителя. В ответе для каждого найденного числа запишите два его наибольших делителя в порядке возрастания.

Решение

Решение 1

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

a=194455

b=194500

k=0

for i in range(a,b+1):

for d in range(2,int(i**0.5)+1):

if pint(d) and i%d==0 and (pint(i//d) or i==d**3):

print(i//d,i)

Решение 2

a=194455

b=194500

# Решето Эратосфена

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for d in range(i*i,b+1,i): m[d]=0

for i in range(a,b+1):

for d in range(int(i**0.5)+1):

if m[d] and i%d==0 and (m[i//d] or i==d**3):

print(i//d,i)

Ответ:

38891 194455

1193 194459

1399 194461

97231 194462

1721 194473

443 194477

97241 194482

4523 194489

17681 194491

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

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

a,b=164700,164752

for i in range(a,b+1):

d=div(i)

if len(d)==6:

print(d[-2],d[-1])

Ответ:

82354 164708

54903 164709

82358 164716

82366 164732

34) (№ 2571 А.Н.Носкин) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [190201; 190220], числа, имеющие ровно 4 различных делителя. В ответе для каждого найденного числа запишите два его наибольших делителя в порядке убывания.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

a,b=190201,119220

for i in range(a,b+1):

d=div(i)

if len(d)==4:

print(d[-1],d[-2])

Ответ:

190201 17291

190202 95101

190214 95107

190219 853

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

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:

d.add(i)

d.add(x//i)

return d

a=190201

b=190260

for i in range(a,b+1):

d2=[]

for i in sorted(div(i)):

if i%2==0: d2.append(i)

if len(d2)==4:

print(d2[-1],d2[-2])

Ответ:

190226 838

190234 17294

190238 2606

190252 95126

190258 758

36) (№ 2574) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [11275; 16328], числа, имеющие ровно 5 различных делителей. В ответе для каждого найденного числа запишите два его наибольших делителя, не равных самому числу, в порядке возрастания.

Решение

Решение 1

a=11275

b=16328

c=int(b**0.25)

m=[1]*(c+1)

m[0],m[1]=0,0

for i in range(int(c**0.5)+1):

if m[i]:

for p in range(i*i,c+1,i):m[p]=0

for i in range(len(m)):

if m[i]:

if a<=i**4<=b:

print(i**2,i**3)

if i**4>b: break

Решение 2

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:

d.add(i)

d.add(x//i)

return list(sorted(d))

a,b=11275,16328

for i in range(a,b+1):

if len(div(i))==5:

d=div(i)

print(d[-3],d[-2])

Ответ:

121 1331

37) (№ 2579 Б.С.Михлин) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [286564; 287270], числа, имеющие максимальное количество различных делителей. Если таких чисел несколько, то найдите максимальное из них. В ответе запишите два числа: количество делителей найденного числа и его наибольший делитель, не равный самому числу.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

maxl=[]

a,b=286564,287270

for i in range(a,b+1):

d=div(i)

if len(d)>=len(maxl):

maxl=d

print(len(maxl),maxl[-2])

Ответ:

112 143520

38) (№ 2585 А.Н.Носкин) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2532000; 2532160] первые пять простых чисел. Выведите найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.

Решение

Решение 1

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

k=0

for i in range(2532000,2532160+1):

if pint(i):

k+=1

print(k,i)

if k==5: break

Решение 2

a,b=2532000,2532160

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(b+1):

if m[i]:

for p in range(i*i,b+1,i): m[p]=0

k=0

for i in range(a,b+1):

if m[i]:

k+=1

print(k,i)

if k==5: break

Ответ:

1 2532007

2 2532067

3 2532071

4 2532083

5 2532107

39) (№ 2588 Д.Ф.Муфаззалов) Совершенным называется число, натуральное число, равное сумме всех своих собственных делителей (то есть всех положительных делителей, отличных от самого́ числа) (например, число 6=1+2+3). ) Выведите каждое совершенное число из диапазона [2; 10000] в количество его собственных делителей в порядке возрастания. Вывод каждого совершенного числа начинайте с новой строки. Числа в строке разделяйте пробелом.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

for i in range(2,10000+1):

if i==sum(div(i)[:-1]): print(i,len(div(i))-1)

Ответ:

6 3

28 5

496 9

8128 13

40) (№ 4410 Л.Шастин) Среди чисел, больших 520000, найти такие, сумма всех делителей которых, не считая единицы и самого числа, образует число-палиндром (например, число 1221: если его «перевернуть», получается то же самое число). Вывести первые пять чисел, удовлетворяющих вышеописанному условию, справа от каждого числа вывести его максимальный делитель.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:

d.add(i)

d.add(x//i)

return list(sorted(d))

k=0

i=520000+1

while k<5:

d=div(i)

if len(d)>2:

s=sum(d[1:-1])

if str(s)==str(s)[::-1]:

k+=1

print(i,d[-2])

i+=1

Ответ:

520211 16781

520993 47363

521653 47423

521947 16837

522077 22699

41) (№ 4416) Найдите 5 составных (не простых) чисел больших 800000, таких, что сумма их наименьшего и наибольшего нетривиальных делителей (не считая единицы и самого числа) делится на 138. В качестве ответа приведите 5 наименьших чисел, соответствующих условию. Формат вывода: для каждого из найденных чисел в отдельной строке запишите само число, а затем сумму его наименьшего и наибольшего нетривиальных делителей.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

k=0

i=800000+1

while k<5:

d=div(i)

if len(d)>3:

if (d[1]+d[-2])%138==0:

k+=1

print(i,d[-2]+d[1])

i+=1

Ответ:

800120 400062

800253 266754

800273 21666

800375 160080

800396 400200

42) (№ 4415) Найдите 5 чисел больших 500000, таких, что среди их делителей есть число, оканчивающееся на 8, при этом этот делитель не равен 8 и самому числу. В качестве ответа приведите 5 наименьших чисел, соответствующих условию. Формат вывода: для каждого из найденных чисел в отдельной строке запишите само число, а затем минимальный делитель, оканчивающийся на 8, не равный 8 и самому числу.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

k=0

i=500000+1

while k<5:

d=div(i)[:-1]

fl=0

for c in d:

if c!=8 and c%10==8: fl=c; break

if fl:

print(i,fl); k+=1

i+=1

Ответ:

500002 178

500004 18

500016 48

500018 58

500020 4348

43) (№ 4211 А.Комков) Обозначим через S сумму делителей числа, не являющихся простыми, кроме единицы и самого числа. Если таких делителей у числа нет, то S равно нулю. Напишите программу, которая перебирает нечетные целые числа, меньшие 912673, в порядке убывания и ищет среди них первые 5 чисел, которые кратны S. Для каждого из найденных чисел в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке убывания найденных чисел.

Решение

Вариант 1 (время работы программы 69.19 с.)

def pint(x):

if x%2==0:return x==2

d=3

while d*d<=x and x%d!=0:d+=2

return d*d>x

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

k=0

i=912673-2

while k<5:

d=div(i)[1:-1]

if len(d)>0:

s=0

for c in d:

if not(pint(c)): s+=c

if s>0 and i%s==0: print(i,s); k+=1

i-=2

Решение 2 (время работы программы 60.04 с.)

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return list(sorted(d))

k=0

a=912673-2

m=[1]*(a+1)

m[0],m[1]=0,0

for i in range(int(a**0.5)+1):

if m[i]:

for p in range(i*i,a+1,i): m[p]=0

while k<5:

d=div(a)[1:-1]

if len(d)>0:

s=0

for c in d:

if not(m[c]): s+=c

if s>0 and a%s==0: print(a,s); k+=1

a-=2

Ответ:

704969 7921

571787 6889

493039 6241

389017 5329

357911 5041

44) (№ 4210 А.Комков) Пусть A – абсолютное значение разности максимального четного и максимального нечетного делителей числа, не считая единицы и самого числа. Если хотя бы одного из таких делителей у числа нет, то считаем значение A равным нулю. Напишите программу, которая перебирает целые числа, большие 250156, в порядке возрастания и ищет среди них первые 5, для которых значение A является простым числом, оканчивающимся на 9. Для каждого из найденных чисел в отдельной строке сначала выводить само число, затем значение A. Строки выводятся в порядке возрастания найденных чисел.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return list(sorted(d))

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

k,b=0,250156+1

while k<5:

d=div(b)[1:-1]

if len(d)>1:

dch=[]

dnch=[]

for c in d:

if c%2:dnch.append(c)

else:dch.append(c)

if len(dch)*len(dnch)!=0:

a=abs(max(dch)-max(dnch))

if pint(a) and a%10==9:

print(b,a)

k+=1

b+=1

Ответ:

250196 62549

250314 41719

250374 41729

250442 125219

250554 41759

45) (№ 4202 Б.Баобаба) Числа-близнецы — это такие простые числа, которые отличаются друг от друга на 2. Найдите все пары чисел-близнецов в диапазоне [3 000 000; 10 000 000]. В ответе запишите количество найденных пар и среднее арифметическое последней пары.

Решение

Решение 1 (время работы программы 8.66 с.)

a,b=3000000,10000000

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for d in range(i*i,b+1,i): m[d]=0

k=0

for i in range(a+1,b-1,2):

if m[i] and m[i+2]:

k+=1

ap,bp=i,i+2

print(k,(ap+bp)//2)

Решение 2 (время работы программы 393.73 с.)

a,b=3000000,10000000

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0:d+=2

return d*d>x

k=0

for i in range(a+1,b-1,2):

if pint(i) and pint(i+2):

k+=1

ap,bp=i,i+2

print(k,(ap+bp)//2)

Ответ: 38048 9999972

46) (№ 2919) Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [177399; 177453], числа, имеющие ровно 6 различных делителей. Выведите для каждого найденного числа два наибольших делителя в порядке возрастания.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return list(sorted(d))

a,b=177399,177453

for i in range(a,b+1):

d=div(i)

if len(d)==6:

print(d[-2],d[-1])

Ответ:

88702 177404

16129 177419

88714 177428

6119 177451

59151 177453

47) (№ 2943 Апробация 19 февраля 2022 года, Москва) Пусть М — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение М считается равным нулю. Напишите программу, которая перебирает целые числа, большие 220 000, в порядке возрастания и ищет среди них такие, для которых значение М оканчивается на 4. Выведите первые пять найденных чисел и соответствующие им значения М.

Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем — значение М.

Строки выводятся в порядке возрастания найденных чисел.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return list(sorted(d))

a,k=220000,0

while k<5:

a+=1

d=div(a)

if len(d)>2 and (d[1]+d[-2])%10==4:

print(a,d[1]+d[-2])

k+=1

Ответ:

220004 110004

220023 73344

220024 110014

220033 20014

220043 1044

48) (№ 1065 Джобс 15.03.2021) Напишите программу, которая находит 10 простых чисел наиболее приближенные к числу 10000000 (10 миллионов). Причем 5 найденных чисел должны быть меньше заданного числа, остальные 5 чисел – больше.

Найденные числа расположите в порядке возрастания. В качестве ответа выведите пары чисел – расстояние от найденного числа до 10000000 и само число.

Например, для числа 50 ответ должен быть следующим:

19 31

13 37

9 41

7 43

3 47

3 53

9 59

11 61

17 67

21 71

Решение

Вариант 1 (время работы 0.137 с.)

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

k,sp=0,[]

i=10**7

while k<5:

i-=1

if pint(i):sp.append(i);k+=1

k,i=0,10**7

while k<5:

i+=1

if pint(i):sp.append(i);k+=1

sp.sort()

for i in sp:print(abs(10**7-i),i)

Вариант 2 (время работы 5.12 с.)

a,b=10**7,a+10**3

m=[1]*(b+1)

m[0],m[1]=0,0

for i in range(int(b**0.5)+1):

if m[i]:

for p in range(i*i,b+1,i):m[p]=0

k,sp=0,[]

i=10**7

while k<5:

i-=1

if m[i]:sp.append(i);k+=1

k,i=0,10**7

while k<5:

i+=1

if m[i]:sp.append(i);k+=1

sp=sorted(sp)

for i in sp:print(abs(10**7-i),i)

Ответ:

63 9999937

57 9999943

29 9999971

27 9999973

9 9999991

19 10000019

79 10000079

103 10000103

121 10000121

139 10000139

49) (№ 1206 Апробация 27.04) Напишите программу, которая ищет среди целых чисел, превышающих 350300, первые шесть чисел, удовлетворяющих условию: сумма всех различных делителей числа, отличных от 1 и самого числа, кратна 13.

В ответе запишите эти шесть пар чисел в порядке возрастания первого числа в паре: число, для каждого такого числа частное от деления на 13 суммы его различных делителей (исключая 1 и само число).

Решение (время работы 0.086 с.)

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

i,k=350300,0

while k<6:

i+=1

d=div(i)[1:-1]

if len(d)>0 and sum(d)%13==0:

print(i,sum(d)//13)

k+=1

Ответ:

350308 26951

350321 630

350333 138

350345 6198

350355 16172

350367 8984

50) (№ 1389) Обозначим через S сумму простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение S равным нулю. Напишите программу, которая перебирает целые числа, большие 250000 в порядке возрастания и ищет среди них такие, для которых значение S не равно нулю и кратно 17.

Программа должна найти первые 5 таких чисел. Для каждого из них в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке возрастания найденных чисел.

Количество строк для записи ответа избыточно.

Решение

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

k=0

i=250000

while k<5:

i+=1

d=div(i)[1:-1] #исключаем из списка 1 и само число**

s=0

if len(d)>0:

for a in d:

if pint(a): s+=a

if s%17==0:

print(i,s)

k+=1

** функция pint() 1(единицу) запишет в простые числа

Ответ:

250003 19244

250015 1649

250028 62509

250059 170

250062 663

51) (№ 1390) Обозначим через M разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю. Напишите программу, которая перебирает целые числа, большие 350000, в порядке возрастания и ищет среди них такие, для которых значение M при делении на 23 даёт в остатке 9.

Запишите первые 6 найденных чисел в порядке возрастания, справа от каждого числа запишите соответствующее значение M.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

k=0

i=350000

while k<6:

i+=1

d=div(i)[1:-1]

s=0

if len(d)>0:

if (max(d)-min(d))%23==9:

print(i,max(d)-min(d))

k+=1

Ответ:

350015 69998

350017 8496

350036 175016

350073 116688

350082 175039

350128 175062

52) (№ 3090) Пусть M(N) = | P(N) - E(N) | (модуль разности) для натурального числа N.

P(N) - сумма абсолютно всех простых делителей числа N.

E(N) - сумма абсолютно всех чётных делителей числа N.

Среди чисел N > 100 000 000 найдите 5 наименьших таких, у которых количество простых делителей совпадает с количеством чётных делителей.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — соответствующие им значения M(N).

Решение

def pint(x):

if x%2==0: return x==2

d=3

while d*d<=x and x%d!=0: d+=2

return d*d>x

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i); d.add(x//i)

return list(sorted(d))

k=0

i=10**8

while k<5:

i+=1

d=div(i)[1:] #исключаем из списка 1**

s=0

kp,kc,sp,sc=0,0,0,0

for a in d:

if pint(a):kp+=1;sp+=a

if a%2==0:kc+=1;sc+=a

if kp==kc:

print(i,abs(sp-sc))

k+=1

** функция pint() 1(единицу) запишет в простые числа

Ответ: 100000034 50000017

100000042 50000021

100000094 50000047

100000118 50000059

100000126 50000063

53) (№ 6210 Н.Сафронов) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру;

— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, не превосходящие 107, для которых выполняются одновременно все условия:

• соответствуют маске *2?2*;

• являются палиндромами;

• делятся на число 53 без остатка;

• количество делителей больше 30.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — сумму делителей.

Решение

def div(x):

m=set()

for d in range(1,int(x**0.5)+1):

if x%d==0: m.add(d);m.add(x//d)

return sorted(m)

for x in range(53,10**7,53):

s=str(x)

if s==s[::-1]:

fl=0

for c in '0123456789':

if ('2'+c+'2') in s: fl=1

d=div(x)

if fl and len(d)>30: print(x,sum(d))

Ответ:

212212 508032

2527252 5588352

4282824 13789440

4626264 11787120

8125218 19595520

8824288 19908504

54) (№ 6095 А.Рогов) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;

– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 108, найдите все числа, соответствующие маске *15*7424, которые делятся без остатка только на одно из чисел 111, 113, 127.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на одно из чисел 111, 113, 127, на которое число делится без остатка.

Решение

for x in range(157424,10**8,+10000):

xs=str(x)

if '15' in xs :

s1=int(x%111==0)

s2=int(x%113==0)

s3=int(x%127==0)

if s1+s2+s3==2:

if x%111==0:d=x//111

elif x%113==0:d=x//113

else:d=x//127

print(x,d)

Ответ:

1587424 14048

15147424 134048

15227424 137184

15457424 121712

28157424 221712

85157424 767184

55) (№ 6055) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;

– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 107 , найдите все числа, соответствующие маске 2?1*67, делящиеся на 159 без остатка.

В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце – соответствующие им результаты деления этих чисел на 159.

Количество строк в таблице для ответа избыточно.

Решение

for x in range(20167//159*159,10**7,159):

s=str(x)

if s[0]=='2' and s[2]=='1' and s[-2:]=='67': print(x,x//159)

Ответ:

2116767 13313

2212167 13913

2418867 15213

2514267 15813

2816367 17713

2911767 18313

56) (№ 5985 Н.Сафронов) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

— символ «?» означает ровно одну произвольную цифру;

— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, не превосходящие 107, соответствующие маске 12*348, делящиеся на число 12 без остатка, и у которых ровно 12 делителей. В ответе запишите в первом столбце таблицы все найденные числа в порядке возрастания, а во втором столбце — максимальный делитель, не равный самому числу.

Решение

Вариант 1

def div(x):

m=set()

for d in range(1,int(x**0.5)+1):

if x%d==0: m.add(d);m.add(x//d)

return sorted(m)

for x in range(100000):

s=str(x)+'348'

if s[:2]=='12' and int(s)%12==0 and len(div(int(s)))==12 : print(s,int(s)//2)

if int(s)>10**7:break

Вариант 2

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:d.add(i);d.add(x//i)

return sorted(list(d))

x=12348//12*12

while x<=10**7:

xs=str(x)

if xs[:2]=='12' and xs[-3:]=='348'and len(div(x))==12:

print(x,div(x)[-2])

x+=12

Ответ:

126348 63174

1203348 601674

1215348 607674

1242348 621174

1257348 628674

1266348 633174

1275348 637674

1287348 643674

57) (№ 5736 Д.Тараскин) Программа перебирает числа больше 109 и выбирает из них числа-палиндромы, у которых наибольший делитель (отличный от 1 и самого числа) кратен 7. Выведите первые 5 чисел, которые выберет программа, и для каждого числа выведите наибольший делитель.

Примечание: Числа-палиндромы — числа, которые читаются одинаково как справа налево, так и слева направо.

Решение

def div(x):

m = set()

for d in range(2, int(x ** 0.5)+1):

if x % d == 0: m.add(d); m.add(x // d);break

return sorted(m)

k = 0

for i1 in range(10**9//7*7, 10**10, 7):

if div(i1)[-1] % 7 == 0 and str(i1) == str(i1)[::-1]:

k += 1

print(i1, div(i1)[-1])

if k == 5: break

Ответ:

1001771001 333923667

1002002001 334000667

1003003001 143286143

1004774001 334924667

1005005001 335001667

58) (№ 5735 Д.Тараскин) Алгоритм перебирает числа больше 106 и выбирает из них те, у которых среди делителей будет хотя бы 20 чисел, являющиеся степенями числа 2, отличные от 1. В ответ запишите первые 5 чисел, которые выберет алгоритм, и для каждого числа выпишите сумму делителей, не являющиеся степенями 2 (отличные от 1 и самого числа). Если делителей кроме степеней 2 в числе не окажется, то выведите 0.

Решение

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return sorted(d)

m2=[1]

for i in range(1,40): m2.append(2**i)

a=2**20

for i in range(1,6):

x=a*i

d=div(x)

m=[]

for c in d:

if not(c in m2): m.append(c)

print(x,sum(m)-int(len(m)>0)*x)

Ответ:

1048576 0

2097152 0

3145728 3145725

4194304 0

5242880 5242875

59) (№ 2594 Д.Тараскин[Уровень: Гроб]*) Найдите все натуральные числа, принадлежащие отрезку [113 000 000; 114 000 000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине чётный делитель.

* - если не умеешь применять основную теорему арифметики

Решение (Идея решения - Число имеет 3 четных делителя, если его можно представить в виде 2*P**2 (где P - простое число))

def p(x):

if x%2==0:return x==2

d=3

while x%d!=0 and d*d<=x:d+=2

return d*d>x

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0:d.add(i);d.add(x//i)

a=[]

for c in d:

if c%2==0:a.append(c)

return sorted(a)

for i in range(113000000,114000000+1,+2):

it=(i//2)**0.5

if int(it)==it and p(it):

print(i,div(i)[-2])

Ответ:

113010578 15034

113191058 15046

113371682 15058

113612738 15074

113733362 15082

113914418 15094

113974802 15098

60) (№ 5225) Пусть N(k) = 9 500 000 + k, где k – натуральное число. Найдите пять наименьших значений k, при которых N(k) нельзя представить в виде произведения трёх натуральных чисел, больших 1. В ответе запишите найденные значения k в порядке убывания, справа от каждого значения запишите наибольший делитель N(k), не равный самому числу.

Решение (Идея решения - )

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return sorted(list(d))

def p(x):

if x%2==0:return 2==x

d=3

while x%2!=0 and d*d<=x: d+=2

return d*d>x

kl,k,b=0,1,[]

while kl<5:

kp=0

d=div(9500000+k)[1:-1]

for x in d:

if p(x):kp+=1

if kp==2: b.append([k,d[-1]]);kl+=1

k+=1

for c in b[::-1]: print(c[0],c[1])

Ответ:

11 39749

9 256757

6 4750003

3 161017

2 4750001

61) (№2850) Рассматриваются целые числа, принадлежащих числовому отрезку [356738; 404321], которые представляют собой произведение двух различных простых делителей. В ответе запишите количество таких чисел и такое из них, простые делители которого отличаются друг от друга больше всего.

Решение (Идея решения - )

def div(x):

d=set()

for i in range(2,int(x**0.5)+1):

if x%i==0 and len(d)<4: d.add(i);d.add(x//i)

return sorted(list(d))

def p(x):

if x%2==0: return x==2

d=3

while x%d!=0 and d*d<=x: d+=2

return d*d>x

r=0;

k=0

for x in range(356738,404321):

d=div(x)

if len(d)==2 and p(d[1]):

k+=1

if r<d[1]-d[0]: r=d[1]-d[0];maxc=x

print(k,maxc)

Ответ: 10013 404258

62) (№5456 Е. Джобс) Найдите числа большие 1000000, сумма и произведение делителей которых нечётны. В ответе укажите наименьшие 6 таких чисел, количество делителей которых больше 40. Для каждого найденного числа выведите количество его делителей. В ответе запишите найденные числа в порядке возрастания, справа от каждого числа запишите количество его делителей.

Решение (Идея решения - )

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return len(d)

k,x=0,1000001

while k<6:

d=div(x)

if d%2 and d>40: print(x,d);k+=1

x+=2

Ответ:

1071225 45

1147041 45

1334025 81

1432809 45

1625625 45

1656369 45

63) (№5456 Е.Джобс) Найдите числа большие 1000000, сумма и произведение делителей которых нечётны. В ответе укажите наименьшие 6 таких чисел, количество делителей которых больше 40. Для каждого найденного числа выведите количество его делителей. В ответе запишите найденные числа в порядке возрастания, справа от каждого числа запишите количество его делителей.

Решение (Идея решения - )

def div(x):

d=set()

for i in range(1,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return len(d)

k,x=0,1000001

while k<6:

d=div(x)

if d%2 and d>40: print(x,d);k+=1

x+=2

Ответ:

1071225 45

1147041 45

1334025 81

1432809 45

1625625 45

1656369 45

64) (№5763 Д.Статный) Найдите все натуральные числа, принадлежащие отрезку [10 000 000; 60 000 000], у которых количество делителей – простое число. В ответе запишите первые 7 чисел с наибольшим количеством делителей, справа от каждого числа запишите количество его делителей. Отсортируйте числа по убыванию количества делителей, а числа с одинаковым количеством делителей – по возрастанию самих чисел.

Решение (Идея решения - )

m=[1]*(int(60000000**0.5)+1)

m[0]=m[1]=0

l=len(m)

for i in range(2,int(l**0.5)+1):

if m[i]:

for j in range(i*i,l,i): m[j]=0

i=2

k=0

while k<7:

if m[i]:

s=2

while i**s<=60000000:

x=i**s

if x>=10000000 and m[s+1] and k<7: print(x,s+1) ;k+=1

s+=2

i+=1

Ответ:

43046721 17

24137569 7

47045881 7

12117361 5

13845841 5

20151121 5

25411681 5

65) (№7500 ЕГЭ-2024) Пусть М – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение М равным нулю. Например, для числа 20 имеем М = 2 + 10 = 12. Напишите программу, которая перебирает целые числа, большие 700 000, в порядке возрастания и ищет среди них такие, для которых М оканчивается на 14. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения М.

Решение

def dev(x):

d=set()

for i in range(2,int(x**0.5)+1):

if x%i==0: d.add(i);d.add(x//i)

return sorted(d)

x=700000

k=0

while k<5:

x+=1

d=dev(x)

if len(d)>=2 and (d[0]+d[-1])%100==14:

print(x,d[0]+d[-1])

k+=1

Ответ:

700024 350014

700045 140014

700049 100014

700224 350114

700233 233414

66) (№3777) Найдите все натуральные числа, принадлежащие отрезку [55 000 000; 60 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа, справа от каждого числа запишите его наибольший нечётный делитель.

Решение (t = 0.065c.)

a=100

p=[1]*a

p[0]=p[1]=0

for i in range(int(a**0.5)+1):

if p[i]:

for j in range(i*i,a,i):p[j]=0

m=[]

for i in range(a):

if p[i]:

x=i**4

while x<=60000000:

if x>=55000000: m.append(x)

x=x*2

for x in sorted(m):

d=x

while d%2==0:d//=2

print(x,d)

Ответ:

55383364 13845841

56796482 28398241

58492928 28561

59105344 923521

59969536 14641

59973152 1874161

67) (№4521) Обозначим через P(N) – произведение 5 наименьших различных нетривиальных делителей натурального числа N (не считая единицы и самого числа). Если у числа N меньше 5 таких делителей, то P(N) считается равным нулю. Найдите 5 наименьших натуральных чисел, превышающих 300 000 000, для которых P(N) оканчивается на 31 и не превышает N. В ответе для каждого найденного числа запишите сначала значение P(N), а затем – наибольший делитель, вошедший в произведение P(N).

Решение (t = 12.769c.)

def div(x):

d=set()

for i in range(2,int(x**0.5)+1):

if x%i==0:d.add(i);d.add(x//i)

return sorted(d)

n=300000001

k=0

while k<5:

m=div(n)

if len(m)>=5:

p=1

for d in m[:5]:p*=d

if p%100==31 and p<=n:print(p,m[4]);k+=1

n+=2

Ответ:

26222031 199

2481831 53

303831 33

1274931 59

143483131 121

68) (№5288 М.Фирсов) На отрезке [100 000; 500 000] найдите такие числа, у которых больше 3 различных простых делителей, причем все они образуют арифметическую прогрессию с разностью отличной от нуля. В качестве ответа запишите найденные числа в порядке возрастания, справа от каждого числа запишите произведение количества простых делителей на разность их арифметической прогрессии.

Решение (t = 35.274c.)

def pr(x):

if x%2==0 or x<=1: return x==2

d=3

while x%d!=0 and d*d<=x:d+=2

return d*d>x

def div(x):

d=set()

for i in range(2,int(x**0.5)+1):

if x%i==0:

if pr(i):d.add(i)

if pr(x//i):d.add(x//i)

return sorted(d)

for x in range(100000,500000):

m=div(x)

if len(m)>3:

r=set()

for i in range(len(m)-1):r.add(m[i+1]-m[i])

if len(r)==1:print(x,len(m)*list(r)[0])

Ответ:

101065 48

107525 24

124729 24

177289 48

236555 24

278185 72

365585 24

494615 24

69) (№2892 М.Фирсов) На отрезке [100 000; 500 000] найдите такие числа, у которых больше 3 различных простых делителей, причем все они образуют арифметическую прогрессию с разностью отличной от нуля. В качестве ответа запишите найденные числа в порядке возрастания, справа от каждого числа запишите произведение количества простых делителей на разность их арифметической прогрессии.

Решение (t = 0.047c.)

def pr(x):

if x%2==0 or x<=1: return x==2

d=3

while x%d!=0 and d*d<=x:d+=2

return d*d>x

k=1

for x in range(4409962+1,4410101+1,2):

if pr(x): print(k,x);k+=1

Ответ:

1 4409981

2 4410019

3 4410041

4 4410047

5 4410061

6 4410079

7 4410097

8 4410101