54 lines
1.7 KiB
Markdown
54 lines
1.7 KiB
Markdown
|
---
|
|||
|
|
id: 5900f5151000cf542c510028
|
|||
|
|
title: 'Завдання 425: З’єднання простих чисел'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302095
|
|||
|
|
dashedName: problem-425-prime-connection
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Два додатних числа $A$ та $B$ вважаються з’єднаними (позначаються "$A ↔ B$"), якщо виконується одна з цих умов:
|
|||
|
|
|
|||
|
|
1. $A$ та $B$ мають однакову довжину і відрізняються тільки однією цифрою; наприклад, $123 ↔ 173$.
|
|||
|
|
2. Додавання однієї цифри зліва від $A$ (або $B$) утворює $B$ (або $A$); наприклад, $23 ≈ 223$ і $123 ≈ 23$.
|
|||
|
|
|
|||
|
|
Назвемо просте число $P$ родичем 2, якщо між 2 і $P$ існує ланцюжок зі з'єднаних простих чисел і жодне число в ланцюжку не перевищує $P$.
|
|||
|
|
|
|||
|
|
Наприклад, число 127 – родич 2. Один з можливих ланцюжків показаний нижче:
|
|||
|
|
|
|||
|
|
$$2 ↔ 3 ↔ 13 ↔ 113 ↔ 103 ↔ 107 ↔ 127$$
|
|||
|
|
|
|||
|
|
Однак 11 та 103 не є родичами 2.
|
|||
|
|
|
|||
|
|
Припустимо, $F(N)$ - сума простих чисел $≤ N$, які не є родичами 2. Можемо переконатися, що $F({10}^3) = 431$ та $F({10}^4) = 78\\,728$.
|
|||
|
|
|
|||
|
|
Знайдіть $F({10}^7)$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`primeConnection()` має повернути `46479497324`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(primeConnection(), 46479497324);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function primeConnection() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
primeConnection();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|