Как узнать простое число или нет?

Рет қаралды 7,792

Күн бұрын

Пікірлер: 39

@dmxumrrk332 Жыл бұрын

Привела на этот канал шутка: «2023 год был непростым, простым будет 2027-й» 😂. Но вопрос, как разложить большое число на множители возникал намного раньше.

@ViktorLazarev-Matematika Жыл бұрын

🤣

@qziix 3 ай бұрын

3:40 начало

@mila_jaaa 2 ай бұрын

Спасибо Вам

@ViktorLazarev-Matematika 2 ай бұрын

пожалуйста)

@daner270 5 ай бұрын

Видео можно уместить в предложение : Чтобы узнать , составное число или нет , нужно проверить делимость этого числа на все простые числа до корня из этого числа . Пример : Простое ли число 49 ? √49=7 , значит проверяем делимость на 2 , 3 , 5 , 7

@ViktorLazarev-Matematika 5 ай бұрын

Да, именно так. Формула Герона тоже в одну строчку пишется, но ее доказательство займет минут 15-20. Здесь рассказано несколько способов определить простое или нет с объяснением почему это так, а не потому что гладиолус.

@henu3dimhoro 6 ай бұрын

я знал этот способ, но не знал почему так работает) спасибо)

@dmitryZONK 2 жыл бұрын

Виктор, привет! Хорошее видео, подписан, жду продолжения!

@ОООПетроСофт 8 ай бұрын

Также есть ещё метод, особенно, когда нужно определить сразу множество простых чисел до какого-либо максимума. Последовательно зачеркнуть некоторые числа, заканчивающиеся на 1,3,7,9 (возможные кандидаты). В результате образуется решето Эратосфена (также есть и другие алгоритмы). Интересный вопрос на засыпку, является ли 1 простым числом и почему (либо не стоит его относить к простым числам).

@ViktorLazarev-Matematika 8 ай бұрын

здесь вопрос про то, как определить простое ли при решении какой-либо задачи, если нет доступа к таблице простых чисел. Решето Эратосфена громоздкий способ. 1 - не простое число. Простые с 2 начинаются.

@ОООПетроСофт 8 ай бұрын

@@ViktorLazarev-Matematika Насчёт громоздкости не согласен, так как вместо деления там используется сложение. Да и вообще алгоритм можно оптимизировать-ускорить. Таблица простых чисел тут же создаётся

@ViktorLazarev-Matematika 8 ай бұрын

@@ОООПетроСофт громоздкость в том, что нужно ВЫПИСАТЬ числа до 1000-10000 и потом их вычеркивать. Также в условиях ЕГЭ/олимпиад нет необходимости в поиске множества простых чисел. Нормальный ученик знает простые до 100, что дает возможность за 5-6 минут проверить на простоту число до 10000. Искать все простые числа - я такую цель не ставил. Мне нужно, чтобы ученик решил задачу. Может ваш алгоритм и сработает выгоднее для данной цели - этого я не знаю.

@ОООПетроСофт 8 ай бұрын

@@ViktorLazarev-Matematika Любая задача в программировании оптимизируется при двух взаимно-противоположных критериях: или вы хотите сэкономить память, но проиграть во времени, либо это будет быстрый алгоритм, но немного нужно выделить ресурсов. Сейчас нет проблем с памятью на ЭВМ запомнить какие-то даже мегабайты. Так что не жадничайте. Тем более что чисел намного меньше будет в этом массиве. 1 бит/число. Жалко?

@ViktorLazarev-Matematika 8 ай бұрын

@@ОООПетроСофт дело в том, что мы говорим о разных ситуациях. Вы говорите с точки зрения программного перебора для программиста. А я показывал в видео как действовать на математике, где на олимпиаде есть только твоя голова, ручка и тетрадь.

@ink718 Жыл бұрын

Спасибо, очень помогло для понимания решения 25 задачи по информатике егэ

@ViktorLazarev-Matematika Жыл бұрын

круто)

@Nikas-Righteous 10 ай бұрын

ужасно много воды, видео на 2 минуты

@VitalayManin Жыл бұрын

давай скажи 2^1277-1 является простым или нет. какой у него делитель.

@livebuzz3685 10 ай бұрын

е6лан?

@ВладосНемерицкий 4 ай бұрын

5 секунд на это потрачу) делитель 1277 если это число простое)

@VitalayManin 4 ай бұрын

@@ВладосНемерицкий не делится

@VitalayManin 4 ай бұрын

@@ВладосНемерицкий если делитель 1277 то какой его второй. делители могут быть только парами!

@VitalayManin 4 ай бұрын

@@ВладосНемерицкий по вашей логике 2^13-1 имеет делитель 13. но число 8191 не делится на 13 следовательно 8191 простое. вот теперь вернемся к 2^1277-1 Как найти делитель.

@Gurgen66 Жыл бұрын

сразу спасибо

@ViktorLazarev-Matematika Жыл бұрын

мгновенное пожалуйста

@ТретьяВолна-э8ъ Жыл бұрын

два простых числа создают идеальный куб. только как это разложить не понимаю. но логически получаеться)

@closer_to_the_unknown 2 жыл бұрын

В задачах на программирование перебор делителей до корня числа - это вполне себе стандартный трюк для оптимизации

@ViktorLazarev-Matematika 2 жыл бұрын

в инфтех классах некоторых это проходят, но по математике об этом нет ни слова в учебниках. Если честно, я сам этот алгоритм себе придумал (подметил) еще малым. А сейчас перед записью видео реально гуглил, а какие алгоритмы есть. А то вдруг есть алгоритм попроще и быстрее и сяду в лужу. Было прикольно увидеть, что это самый быстрый способ узнать точный результат...

@ViktorLazarev-Matematika 2 жыл бұрын

@Василий Сидельников нет, я неточно выразился судя по всему во фразе "А сейчас перед видео реально гуглил". я имел в виду, что я будучи лет 12, подметил и доказал себе этот факт и пользовался им, так как лучшего не придумал (я учил математику сам без учителя, ей было не до меня). А перед записью этого видео я как раз и посмотрел какие алгоритмы существуют и обрадовался, что мой алгоритм оказался самым выгодным из тех, что дают точный результат. Подправил свой коммент выше, чтобы не было двусмысленности)