Каков самый большой делитель числа 600851475143, являющийся простым числом?

@Freeze_Breeze · Регистрация: 12.01.2016

Товарищи, помогайте, потому что у меня сейчас случится дикий приступ. Вообщем, задача такая: Каков самый большой делитель числа 600851475143, являющийся простым числом?
Из числа 600851475143 у меня получаются такие множители [71, 839, 1471, 6857] и среди этих чисел нужно найти наибольшее простое, для начала ищу простые числа, алгоритм который я нашёл на просторах интернета показывает мне, что все числа составные, все 4 числа есть составными, но я заведомо знаю, что число 71 является простым, но алгоритм так не считает. Вопрос, где я накосячил и правильно ли я переписал этот алгоритм?

JavaScript
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
let num = 600851475143, 
    arr = [],
    k = 2,
    j = 0;
 
//Находим множители числа
while (num !== 1) {
    if (num % k === 0) {
       num /= k;
       arr.push(k);
    } else if (num % k !== 0) {
        k++;
    };
};
 
console.log(arr); //[71, 839, 1471, 6857]
 
//Находим простые числа среди множителей
for (let i = 0; i < arr.length; i++) {
    if (k * k <= arr[i] && j !== 1) {
        if (arr[i] % b === 0) {
            j = 1;
        } else {
            k += 1;
        };  
    } else if (j === 1) {
        console.log('Простое число');
    } else {
        console.log('Составное число');
    };
};

@Freeze_Breeze · 10.08.2022, 15:50 **[ТС]**

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

вот мой окончательный вариант...

Спасибо конечно, за ответ, но я прихожу на форум за разъяснением, найти и скопипастить я могу и сам, это не сложно, но так я ничему не научусь.

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

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

Тогда код для первого элемента будет следующий

И для последующих он будет такой же, ведь у нас цикл идёт for (let i = 0; i < arr.length; i++) начинается с i_го элемента массива с шагом i++, то есть каждую итерацию будет i + 1 и пока условие не станет ложным, то есть i < arr.length, если i будет больше длины массива, тогда false и цикл завершает свою работу.

krvsa · 10.08.2022, 15:55

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

console.log(arr); //[71, 839, 1471, 6857]

Это и есть простые числа. Достаточно просто взять последнее число...

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

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

я прихожу на форум за разъяснением

Вот тебе разъяснение:
- перебирая числа от 2 до ..., мы находим простое число которое является делителем исходного
- затем исключаем кратность этому числу, деля исходное на найденное возможное количество раз
- после этого цикл повторяется...

Последнее число-делитель это наш ответ.

@Balanaar · 10.08.2022, 15:55

Freeze_Breeze, это хорошо конечно, только вы неправильно его не реализовали. Ещё раз просмотрите его внимательно по строчкам.
krvsa, ваш код безусловно хорош и прост. Однако ТС хочет разобраться в своих ошибках, а не ищет готовых решений, как 98% остальных форумчан.

krvsa · 10.08.2022, 16:00

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

JavaScript
1
2
3
4
5
6
7
8
while (num !== 1) {
    if (num % k === 0) {
       num /= k;
       arr.push(k);
    } else if (num % k !== 0) {
        k++;
    };
};

Особо мудрить далее не нужно

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//let num = 680
let num = 600851475143
let k = 2
let div
 
while (num !== 1) {
    if (num % k) {
        k++;
    } else {
       num /= k;
       div = k;
    };
};
console.log(k)

@Freeze_Breeze · 10.08.2022, 16:02 **[ТС]**

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

Это и есть простые числа. Достаточно просто взять последнее число...

Если это простые числа, тогда достаточно и такого цикла:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let num = 600851475143, 
    arr = [],
    k = 2,
    j = 0;
 
//Находим множители числа
while (num !== 1) {
    if (num % k === 0) {
       num /= k;
       arr.push(k);
    } else if (num % k !== 0) {
        k++;
    };
};
 
console.log(arr); //[71, 839, 1471, 6857]

Но ведь это делители/множители мы нашли, но ни как не простые числа или я чего то не понимаю?

Добавлено через 1 минуту
аааааааааааа то, есть вы хотите сказать, что делители/множители и будут простыми числами, я правильно понял?

krvsa · 10.08.2022, 16:03

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

но ни как не простые числа

Проверь

https://poschitat.online/yavly... lo-prostym

@Balanaar · 10.08.2022, 16:05

Freeze_Breeze, ещё раз...

JavaScript
1
2
3
4
5
6
7
console.log(arr); //[71, 839, 1471, 6857]
 
k = 0;
//Находим простые числа среди множителей
for (let i = 0; i < arr.length; i++) {
    // Первая итерация: i = 0, arr[i] = 71
};

Заходим в первую итерацию, подставляя значения:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
    if (0 * 0 <= 71 && 0 !== 1) { // Истина
    if (71 % 0 === 0) { // NaN === 0 => Ложь
        j = 1;
    } else {
        k += 1; // k = 1
    };  
    } else if (j === 1) { // Не выполнится
        console.log('Простое число' + ' ' + arr[i]);
    } else { // Не выполнится
        console.log('Составное число');
    };
// Всё. Алгоритм для числа 71 завершён в 1 шаг. Переходим к числу 839

krvsa · 10.08.2022, 16:09

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

делители/множители

Ты просто сам себя запутываешь.
У числа есть "делители"... Но не все делители есть простые числа.

Применяемый тобой алгоритм ищет именно простые числа, затем удаляет их кратность.
Это хорошо видно на примере числа 680.
Там сначала удаляется кратность двойки (3 раза), далее опять идут делители которые простые числа...
Но если 680 умножить на 5 или 17 - можно будет опять наблюдать как убирается кратность этим числам.

@Freeze_Breeze · 10.08.2022, 16:14 **[ТС]**

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

Ты просто сам себя запутываешь.
У числа есть "делители"... Но не все делители есть простые числа.

Я ранее писал какой то алгоритм, но потом его удалил, там были и простые числа (те что сейчас получились) и ещё куча других, там было около 16-ти делителей, но потом я понял, что это фигня и переписал на вот этот, который как оказывается находит простые делители числа. И просто остаётся найти большее среди них.

krvsa · 10.08.2022, 16:15

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

И просто остаётся найти большее среди них.

Просто взять последнее!

@Freeze_Breeze · 10.08.2022, 16:34 **[ТС]**

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

Просто взять последнее!

Каков самый большой делитель числа 600851475143, являющийся простым числом?
Получается типо так?

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let num = 600851475143, 
    arr = [],
    k = 2;
 
//Находим множители числа
while (num !== 1) {
    if (num % k === 0) {
       num /= k;
       arr.push(k);
    } else if (num % k !== 0) {
        k++;
    };
};
 
console.log(arr[arr.length - 1]); //6875

Ииии типо всё? Задача решена?

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

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

ещё раз...

Я понял, что это лишнее было.

Добавлено через 11 минут
krvsa, Balanaar, Большое спасибо. Я всё понял. Я понял как работает это цикл for (let i = 0; i < arr.length; i++) { и понял, что он вообще не нужен, так как первым циклом while я уже нашёл простые числа, просто сам не подозревал этого, и опять пытался среди четырёх делителей найти простые числа, когда они уже являются простыми и просто нужно было вывести большее из них, то есть последнее. Большое спасибо. Всё понятно.

Новые блоги и статьи Все статьи Все блоги /
[golang] Insert Delete GetRandom O(1) (Leetcode: 380) alhaos 16.06.2026 Insert Delete GetRandom O(1) Сложность: Medium Источник: LeetCode 380 Задача Реализовать структуру данных RandomizedSet, которая поддерживает следующие операции за O(1) в среднем:	Свет в конце тоннеля kumehtar 16.06.2026 Поймал себя на одной мысли. Раньше мне всегда казалось неправильным жить без чёткого понимания, куда всё идёт. Будто я иду по дороге судьбы, но не знаю, куда она ведёт. А раз не знаю — значит,. . .	[golang] Реализация стека с поддержкой получения минимального элемента за O(1) alhaos 16.06.2026 Min Stack Сложность: Medium Источник: LeetCode 155 Задача: Реализовать стек который поддерживает push, pop, top и получение минимального элемента за O(1). Методы:	[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. alhaos 10.06.2026 Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .
[golang] Состояние гонки (race condition) alhaos 10.06.2026 Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .	Взрослые отношения, и почему они не получаются kumehtar 09.06.2026 Когда в детстве ребёнок не получает от родителей чего-то важного, он лишается не просто приятных переживаний, а основы для формирования определённых внутренних качеств и навыков. Если ребёнок не. . .	[golang] Worker Pool alhaos 09.06.2026 Worker Pool Worker Pool — паттерн конкурентной обработки задач в Go. Суть: фиксированное количество горутин-воркеров читают задачи из общего канала и пишут результаты в общий канал результатов. . . .	[golang] Pipeline alhaos 08.06.2026 Pipeline Pipeline — паттерн конкурентной обработки данных в Go. Суть: данные проходят через цепочку независимых стадий, каждая из которых работает в своей горутине и общается с соседями через. . .

@Balanaar 2463 / 1769 / 625 Регистрация: 11.07.2016 Сообщений: 4,067
	10.08.2022, 15:55
	Freeze_Breeze, это хорошо конечно, только вы неправильно его не реализовали. Ещё раз просмотрите его внимательно по строчкам. krvsa, ваш код безусловно хорош и прост. Однако ТС хочет разобраться в своих ошибках, а не ищет готовых решений, как 98% остальных форумчан. 1