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

ded-Egor / euler03

Save ded-Egor/23124d6f4e63844a19ee8dfab7c6620d to your computer and use it in GitHub Desktop.

Проект Эйлера. Задача 3. Python

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Footer

© 2024 GitHub, Inc.

You can’t perform that action at this time.

Простой делитель числа

Простые делители числа 13195 — это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом? Не совсем понимаю проблему в своем алгоритме. По сути, мы должны найти корень из заданного числа, после чего сделать проверку на простоту этого делителя. Но в моём решении создается не простое число. Результат: 486847 — не простое число

using System; using System.Collections.Generic; namespace Test < class Program < static void Main(string[] args) < long number = 600851475143; int chislo = Convert.ToInt32(Math.Sqrt(number)); int res = 0; Listlists = new List(); for(int i = 1; i < chislo; i++) < if(number % i == 0) < lists.Add(i); >> for(int i = 0; i < lists.Count; i++) < for(int j = 2; j < lists.Count; j++) < if(lists[i] % j != 0 && lists[i] >1) < res = lists[i]; >> > Console.WriteLine(res); > > > 

Отслеживать
задан 28 июл 2021 в 8:28
Jeffrey Willis Jeffrey Willis
89 7 7 бронзовых знаков
половина делителей теряется, потому что добавляется только один из них
28 июл 2021 в 8:41

По сути, мы должны найти корень из заданного числа, после чего сделать проверку на простоту этого делителя — нет, конечно. По вашему, если число не является квадратом просто числа, то у него и нет простых делителей?

28 июл 2021 в 9:22

Просто раскладывайте на простые множители, стандартно по возрастанию множителя. Последний и будет решением.

Где ошибка в решении?

У вас number в int не помещается. А вы цикл гоните от 2 до number. У вас условие i < number в цикле будет всегда выполнятся - потому что ну не может int i быть больше number.

edit: И вообще логика проверки на простоту у вас сломана. del = i выполнится для любого j, такого что i на него не делится. Т.е. если i=6, то при j=5 вы dеl перезапишите. Вам надо в цикле устанавливать bool flag. И, после цикла на него смотреть.

Ответ написан более двух лет назад
Нравится 2 9 комментариев

тут бы еще условие поменять на i*i
Wataru @wataru Куратор тега C++

galaxy, Я бы вообще по-другому делал. Я бы сразу сокращал number на i, пока делится. Это самое i в таком подходе всегда будет простым. Даже внутреннего цикла не надо.

til_down @til_down Автор вопроса

И вообще логика проверки на простоту у вас сломана. del = i выполнится для любого j, такого что i на него не делится.

Спасибо за замечание. Исправил, проверил на числах поменьше. Работает, вроде, правильно. Но основная проблема сохранилась. Все еще ничего не выводит. Быть может с++ не может справиться с такими огромными значениями? И надо подойти к решению, используя алгоритмы для работы с большими числами?
Обновленный код:

#include using namespace std; long long number = 600851475143; long long del = 0; bool flag = true; int main(int argc, char const *argv[]) < for (long long i = 2; i < number; i++) < flag = true; if (number % i == 0) < for (long long j = 2; j < i; j++) < if (i % j == 0) < flag = false; break; >> if (flag) del = i; > > cout

Wataru @wataru Куратор тега C++

til_down, Конечно, оно не справляется. Один только цикл до 600851475143 будет выполнятся минут 10. А там внутри ведь еще и цикл для проверки. Я думаю, ваше решение будет пару часов работать.

Однако, если вы будете сокращать number на i ( number /= i; ), пока оно делится (может, придется кучу раз сокращать), то не надо внутреннего цикла — i всегда будет простым.

Вторая оптимизация — можно остановиться, когда i*i > number. Тогда оставшееся number, если оно больше 1, будет каким-то простым числом.

Это все работает, потому что мы поддерживаем инвариант — number не делится ни на одно число, меньшее i (кроме 1, конечно). Поэтому надо циклом while сокращать i пока можно. Поэтому, если number делится на i, то i — простое. Ведь иначе был бы меньший i делитель number. Поэтому при i*i>number, number — простое, ведь иначе у него был бы какой-то делитель, меньший i.

Это решение будет работать сильно быстрее.

til_down @til_down Автор вопроса

Wataru, большое спасибо! Решил использовать второй метод. Ответ вывел правильно.
Я решил разобраться, почему данный способ работает, но не смог понять. Потому как, работает он не для всех чисел. К примеру, если в качестве вводимого числа использовать 246 — программа выводит 3, хотя должна вывести 41.Можете объяснить почему?

И ещё, если есть возможность, можете написать(в виде кода) ваш способ решения —

Однако, если вы будете сокращать number на i (number /= i;), пока оно делится (может, придется кучу раз сокращать), то не надо внутреннего цикла — i всегда будет простым.

И объяснить как он работает?

Заранее спасибо, вы мне очень помогли)

Wataru @wataru Куратор тега C++

Вот этот код выведет все простые делители числа.

long long i = 2; while (i*i ++i; > if (number > 1) cout 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

x = 0 num = 600851475143 sp = [] n = num def pr(n): for x in range(2, n - 1): if not n % x == 0 or n == 1: return True else: return False for i in range(1, num): if pr(i) == True and n % i == 0: sp.append(i) n = num / i if n == 1: break print(max(sp))

1 2 3 4 5 6 7 8

num = 600851475143 d = 2 while num != 1 and d*d  num: if num % d == 0: num //= d else: d += 1 print(num)

while num != 1 and d*d  num:

while d*d  num:

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

def divisors(n): yield 1 i = 2 while i**2  n: if n % i == 0: yield i j = n // i if j != i: yield j i += 1 def prime(n): if n  2: return False if n % 2 == 0: return n == 2 if n % 3 == 0: return n == 3 i, s = 5, 2 while i**2  n: if n % i == 0: return False i += s s = 4 if s == 2 else 2 return True print(max(i for i in divisors(600851475143) if prime(i)))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def isPrime(n): i=2 while(i*in): if n%i==0: return False return True #n=600851475143 def max_prime_div(n): k=3 while(True): if n%k==0: r=n//k if isPrime(r): return r k+=2 print(max_prime_div(600851475143))

1 2 3 4 5 6 7 8 9 10 11 12 13 14

from math import sqrt n = 600851475143 i = 2 while n % i != 0 or any(n // i % j == 0 for j in range(2, int(sqrt(n // i))+1)): if i == 2: i = 3 elif i == 3: i = 5 else: i += (9 - i % 6) // 2 print(n // i)

1 2 3 4 5 6 7 8 9

num = 600851475143 d = 2 while num != 1 and d*d  num: if num % d == 0: num //= d else: d += 1 print(num) # Используется свойство числа , макс. делитель меньше или равен квадратному корню числа

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

''' Делается с помощью 2 методов первый просто проверяет число на простату) второй ищет самый больший делитель при условии что ] максимально допустимый делитель меньше или равен квадратному корню числа(с округлением) [given_number ** (0.5)] ''' def prime_number(number: int): a = number k = 0 for i in range(2, a // 2 + 1): if (a % i == 0): k = k + 1 if (k  0): return True def high_prime_number_division(given_number: int): list_num = [] for element in range(2, given_number): if element  round(given_number ** (0.5)): if given_number%element==0: if prime_number(element): list_num.append(element) else: return list_num[-1] print(high_prime_number_division(600851475143))