Укорачиваемые простые числа

@_Даниил_ · Регистрация: 21.12.2019

Студворк — интернет-сервис помощи студентам

Наткнулся на задачу:
Число 3797 обладает интересным свойством. Будучи само по себе простым числом, из него можно последовательно выбрасывать цифры слева направо, число же при этом остается простым на каждом этапе: 3797, 797, 97, 7. Точно таким же способом можно выбрасывать цифры справа налево: 3797, 379, 37, 3.

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

ПРИМЕЧАНИЕ: числа 2, 3, 5 и 7 таковыми не считаются.
В целом я решил эту задачу, но как по закону подлости 11-ое число находится очень долго, можете предложить оптимизированную версию?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from math import sqrt
 
 
def easy_number(n, lst):
    for i in range(2, n + 1):
        for j in lst:
            if j > int((sqrt(i)) + 1):
                lst.append(i)
                break
            if (i % j == 0):
                break
        else:
            lst.append(i)
    return lst
 
 
def carve(lst, i):
    if i in lst:
        return True
    else:
        return False
 
 
def nopa(i,s,lst):
    f = True
    k = True
    easy_number(i, lst)
    if carve(lst, i):
        i = str(i)
        for q in range(1, len(i)):
            a = i[q:]
            a = int(a)
            if carve(lst, a):
                f = True
            else:
                f = False
                break
        for fo in range(1, len(i)):
            bo = i[:-fo]
            bo = int(bo)
            if carve(lst, bo):
                k = True
            else:
                k = False
                break
        if f and k:
            s.append(int(i))
    return s
 
s = []
lst = []
i=8
while len(s)!= 11:
    i=int(i)
    i=i+1
    f = True
    k = True
    easy_number(i, lst)
    if carve(lst, i):
        i = str(i)
        for q in range(1, len(i)):
            a = i[q:]
            a = int(a)
            if carve(lst, a):
                f = True
            else:
                f = False
                break
        for fo in range(1, len(i)):
            bo = i[:-fo]
            bo = int(bo)
            if carve(lst, bo):
                k = True
            else:
                k = False
                break
        if f and k:
            s.append(int(i))
print(s)

единственное попрошу написать как вы это сделали т.к. я новечек), в заранее спасибо!

@Miryz · 07.07.2020, 18:10

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
lst = []
num = 9
def Slave(x):
    s = 2
    while s**2 <= x and x % s != 0:
        s += 1
    return s**2 > x
while len(lst) < 11:
    i = 0
    while Slave(int(str(num)[i:])) and Slave(int(str(num)[:len(str(num)) - i])):
        i += 1
        if i == len(str(num)): break
    if i == len(str(num)):
        lst.append(num)
    num += 2
print(*lst)

@Welemir1 · 07.07.2020, 18:35

Сообщение от _Даниил_

новечек

новИчОк

Сообщение от _Даниил_

айдите единственные одиннадцать простых чисел, из которых можно выбрасывать цифры как справа налево, так и слева направо

а почему всего 11, у меня вроде больше получается?
вот пример таких чисел, или я что-то не так понял?

Добавлено через 23 секунды
Miryz, функции с большой буквы? это же не наши методы)

@Miryz · 07.07.2020, 19:04

Welemir1, это такое слово...

@Welemir1 · 07.07.2020, 19:09

Сообщение от Miryz

это такое слово...

https://www.python.org/dev/peps/pep-0008/

@Miryz · 07.07.2020, 19:12

Welemir1, знаю...

@Black Fregat · 07.07.2020, 19:21

Сообщение от Welemir1

у меня вроде больше получается?

А чего вдруг единички в список простых попали?

@Welemir1 · 07.07.2020, 19:23

Black Fregat, упс, спасибо, проглядел

@Miryz · 07.07.2020, 19:26

Welemir1,

@Welemir1 · 07.07.2020, 19:46

Сообщение от _Даниил_

но как по закону подлости 11-ое число находится очень долго

сколько? у меня секунд 6-7

@Black Fregat · 07.07.2020, 19:57

Код решета честно взят с rosettacode.org:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
N = 10000000
 
def rwh_primes(n):
  sieve = [True] * n
  for i in range(3,int(n**0.5)+1,2):
    if sieve[i]:
      sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
  return [2] + [i for i in range(3,n,2) if sieve[i]]
 
primes = rwh_primes(N)
 
def cut_l(x):
  return int(str(x)[1:])
 
res_l = []
for p in primes[4:]:
  cut = cut_l(p)
  if cut in (primes if p < 100 else res_l):
    res_l.append(p)
 
def cut_r(x):
  return x // 10
 
res_r = []
for p in primes[4:]:
  cut = cut_r(p)
  if cut in (primes if p < 100 else res_r):
    res_r.append(p)
 
print(*(v for v in res_l if v in res_r))

Получилось

Code
1
23 37 53 73 313 317 373 797 3137 3797 739397

Добавлено через 46 секунд
Секунд 30

@Welemir1 · 07.07.2020, 20:00

Сообщение от Black Fregat

Секунд 30

может комп слабоват? мое за 6-7 секунд и то я думаю нахождение простого числа можно ускорить наверное

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def is_prime(n: int) -> bool:
    if n == 2:
        return True
    if n % 2 == 0 or n < 2:
        return False
    i = 3
    while i ** 2 <= n:
        if n % i == 0:
            return False
        i += 2
    return True
 
 
def is_partially_prime(value: int) -> bool:
    if not is_prime(value):
        return False
    str_value = str(value)
    parts = [str_value[:i] for i in range(1, len(str_value))]
    parts += [str_value[-i:] for i in range(1, len(str_value))]
    for e in sorted(parts):
        if not is_prime(int(e)):
            return False
    return True
 
 
if __name__ == '__main__':
    generator_ = (e for e in range(8, 1_000_000) if is_partially_prime(e))
    for _ in range(11):
        print(next(generator_))

@Miryz · 07.07.2020, 20:26

Welemir1,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from datetime import datetime
import time
start_time = datetime.now()
lst = []
num = 9
def Slave(x):
    s = 2
    if x != 1:
        while s ** 2 <= x and x % s != 0:
            s += 1
        else:
            return s ** 2 > x
    else: return False
while len(lst) < 11:
    i = 0
    while Slave(int(str(num)[i:])) and Slave(int(str(num)[:len(str(num)) - i])):
        i += 1
        if i == len(str(num)): break
    if i == len(str(num)):
        lst.append(num)
    num += 2
print(*lst)
print(datetime.now() - start_time)
23 37 53 73 313 317 373 797 3137 3797 739397
0:00:36.730704

Добавлено через 1 минуту

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from datetime import datetime
import time
start_time = datetime.now()
 
 
def is_prime(n: int) -> bool:
    if n == 2:
        return True
    if n % 2 == 0 or n < 2:
        return False
    i = 3
    while i ** 2 <= n:
        if n % i == 0:
            return False
        i += 2
    return True
 
 
def is_partially_prime(value: int) -> bool:
    if not is_prime(value):
        return False
    str_value = str(value)
    parts = [str_value[:i] for i in range(1, len(str_value))]
    parts += [str_value[-i:] for i in range(1, len(str_value))]
    for e in sorted(parts):
        if not is_prime(int(e)):
            return False
    return True
 
 
if __name__ == '__main__':
    generator_ = (e for e in range(8, 1_000_000) if is_partially_prime(e))
    for _ in range(11):
        print(next(generator_))
 
print(datetime.now() - start_time)
0:00:09.700011

@Black Fregat · 07.07.2020, 20:54

Сообщение от Welemir1

может комп слабоват?

Просто лишний ноль в N написал )

@Welemir1 · 07.07.2020, 21:01

Black Fregat, то есть теперь за 3 секунды?

@Black Fregat · 07.07.2020, 22:46

Code
1
2
23 37 53 73 313 317 373 797 3137 3797 739397
0:00:01.901101

Новые блоги и статьи Все статьи Все блоги /
Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	07.07.2020, 19:04
	Welemir1, это такое слово... 0

@Miryz 291 / 131 / 58 Регистрация: 24.11.2019 Сообщений: 532
	07.07.2020, 19:12
	Welemir1, знаю... 0

@Welemir1 Автоматизируй это! 7392 / 4819 / 1246 Регистрация: 30.03.2015 Сообщений: 13,695 Записей в блоге: 29
	07.07.2020, 19:23
	Black Fregat, упс, спасибо, проглядел 0

@Welemir1 Автоматизируй это! 7392 / 4819 / 1246 Регистрация: 30.03.2015 Сообщений: 13,695 Записей в блоге: 29
	07.07.2020, 21:01
	Black Fregat, то есть теперь за 3 секунды? 0

Укорачиваемые простые числа

Решение