Поиск  Пользователи  Правила  Войти
Форумы "Планета Excel" » Вопросы по Microsoft Excel
Страницы: 1
RSS
Программа, проверяющая число на простоту
 
#1
20.05.2018 16:10:10
Здравствуйте!

Помогите, пожалуйста, решить задание. Никак не догоняю.
Реализовать программу, проверяющую заданное пользователем число на простоту.
Простые числа имеют ровно 2 делителя: единицу и само число. Ответ в виде сообщения.
 
 
 
#2
20.05.2018 16:12:47
VBA или формулой?
Если в мире всё бессмысленно, — сказала Алиса, — что мешает выдумать какой-нибудь смысл? ©Льюис Кэрролл
 
 
 
#3
20.05.2018 16:20:15
Цитата
Bema написал:
VBA или формулой?
VBA
 
 
 
#4
20.05.2018 16:22:33
Доброе время суток
Цитата
cheesepls написал:
Никак не догоняю
А по конкретнее? Решето Эратосфена
Цитата
Bema написал:
формулой
Коллега, а как?!
Изменено: Андрей VG - 20.05.2018 16:23:08
 
 
 
#5
20.05.2018 16:32:52
Цитата
cheesepls написал:
Реализовать программу
Понятно, что макрос, но можно и такой достаточно простой формулой массива:
=ЕСЛИ(ИЛИ(СУММ(--(0=ОСТАТ(A1/СТРОКА(СМЕЩ(A1;;;A1));1)))=2;A1=1);"Простое";"Составное")
Если в мире всё бессмысленно, — сказала Алиса, — что мешает выдумать какой-нибудь смысл? ©Льюис Кэрролл
 
 
 
#6
20.05.2018 16:59:34
Здравствуйте, Bema! Симпатичная формула, но, начиная с определенного значения дает, естественно, ошибку. Кроме того, проверять делители можно до квадратного корня из числа.
Владимир
 
 
 
#7
20.05.2018 17:02:19
Цитата
sokol92 написал:
начиная с определенного значения дает, естественно, ошибку.
Здравствуйте, sokol92, Видимо строки закончились.
Если в мире всё бессмысленно, — сказала Алиса, — что мешает выдумать какой-нибудь смысл? ©Льюис Кэрролл
 
 
 
#8
20.05.2018 17:22:49
Цитата
Bema написал:
Видимо строки закончились
Да, конечно. Тема непонятна. Достаточно простого поиска в сети, например "prime number vba"
Изменено: sokol92 - 20.05.2018 17:24:58
Владимир
 
 
 
#9
20.05.2018 19:34:21
Когда-то писал довольно шустрый алгоритм. Число до 30 знаков отрабатывает за секунды. Реализовано как отдельная программа.Решение на С++. Можно, конечно положить в dll или xll, открывать в Excel или в VBA. Но кому это нужно, обычно хотят, что бы все расжевали и код с файлом примером приложили, как готовое решение. Поэтому оставлю ссылку для спецов форума и энтузиастов (будет спрос, можно и библу набросать).
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#10
20.05.2018 19:53:18
Здравствуйте, Виталий! Можно добавить соответствующие функции в Ваш интерфейс к MPIR.
Владимир
 
 
 
#11
20.05.2018 20:05:15
sokol92, Приветствую! Да, можно положить в СОМ, как свойство или метод класса целых чисел, возвращающий массив решений или перечисление в строке через разделитель (в проекте на библиотеках MPIR)
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#12
20.05.2018 20:11:40
Именно это я и имел в виду. Эффективность MPIR в такого рода задачах на несколько порядков выше, чем кода на VBA.
Владимир
 
 
 
#13
20.05.2018 20:22:26
Да это так, узкие места в этих библиотеках написаны на ассемблере (быстрее асма ничего не работает). Можно реализовать именно проверку на простоту - да/нет, это будет ещё быстрее, чем поиск делителей в моем решении. Мое решение, если вы почитаете блог, тоже основано на MPIR, многопоточности, оптимизации wheel factorization и некоторых других идеях оптимизации.
Изменено: bedvit - 20.05.2018 20:26:11
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#14
20.05.2018 20:41:06
Если это будет интересно форуму, добавлю свойство в СОМ, и в VBA "Программа, проверяющая число на простоту" будет размером/состоять из... 3 строк :)
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#15
20.05.2018 21:07:47
Bema, ну снова вы за смещение, когда уж   от летучести то через a1:index(A:A  …. :-)
Позволю немного оптимизнуть
=IF(SUM(--(0=MOD(A1/ROW(A1:INDEX(A:A;A1/2));1)))=1;"Простое";"Составное")
диапазон проверки сокращаем в двое, понятно что максимальный делитель может быть не более половины. Так как Ну совершенно очевидно, что на 1 и на само себя все числа делятся, по этому OR можно убрать и сравнивать с 1 так как до самого числа мы уже не добираемся.
 
Изменено: БМВ - 20.05.2018 21:08:38
По вопросам из тем форума, личку не читаю.
 
 
 
#16
20.05.2018 21:22:31
БМВ,
sokol92 обращал внимание, что верхний предел можно ограничить КОРЕНЬ(А1), а не А1/2
если в А1 1 млн. есть разница перебирать значения от 2 до 1000 или до 500тыс.?
Изменено: Ігор Гончаренко - 20.05.2018 21:23:03
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
 
 
 
#17
20.05.2018 21:32:25
Ігор Гончаренко,
Игорь, /2 первое что пришло на ум, а то что Владимир написал я не видел.
По вопросам из тем форума, личку не читаю.
 
 
 
#18
22.05.2018 09:06:01
Ігор Гончаренко, БМВ,  вы смотрелм ссылку от Андрея? Как по мне, Решето Эратосфена уже очень неплохой алгоритм, а там ещё и модификации есть…
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
 
 
#19
22.05.2018 10:15:42
Jack Famous, предполагаю, нужно готовое решение. Потому как и Андрей давал ссылку и я на свой блог, где прописан быстрый алгоритм нахождения простых чисел. У меня и решение в открытом доступе, правда не на VBA, но на VBA можно реализовать похожий или сделать библу, добавить в существующий проект (см.посты 10-14). Но, это же надо читать, вникать, писать код :)
Изменено: bedvit - 22.05.2018 10:17:03
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#20
22.05.2018 10:25:02
Jack Famous,  Алгоритмом то каждый может, вы формулой попробуйте :-)
собственно по итогу
=IF(SUM(--(0=MOD(A1/ROW(A1:INDEX(A:A;SQRT(A1)));1)))=1;"Простое";"Составное")

По мотивам следующего поста от MCH

=CHOOSE(IF(INT(A1)<>A1;;IF(A1<4;1;IF(MOD(A1;2)=0;;IF(SUM(--(0=MOD(A1/((ROW($A$2:INDEX($A:$A;SQRT(A1)/2))-1)*2+1);1)))=1;1))))+1;"Составное";"Простое")
Изменено: БМВ - 22.05.2018 12:33:55
По вопросам из тем форума, личку не читаю.
 
 
 
#21
22.05.2018 10:38:24
если нужно на VBA (обрабатывает 15-значные числа)
Код
Function IsPrime(n As Double) As Boolean
    Dim i As Long
    If Fix(n / 2) * 2 = n And n > 3 Then Exit Function
    For i = 3 To Int(Sqr(n)) Step 2
        If Fix(n / i) * i = n Then Exit Function
    Next i
    IsPrime = True
End Function
 
 
 
#22
22.05.2018 12:08:38
bedvit, в вашу беседу с sokol92 я вообще предпочёл не встревать — там что-то метафизическое для меня))))
БМВ, да я к слову о ваших с Ігорем Гончаренко оптимизациях писал — вы там пределы и границы как раз обсуждали, а по ссылке именно эти вещи и описаны подробно  :)
Изменено: Jack Famous - 22.05.2018 13:40:02
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
 
 
#23
22.05.2018 16:13:32
Цитата
Jack Famous написал:
там что-то метафизическое для меня
Никакой метафизики, чистая математика. В свое время профессиональный интернациональный коллектив специалистов по теории чисел создал высокооптимизированную библиотеку MPIR, которая, в частности, работает с большими целыми числами. Виталий (bedvit) взял на себя тяжкий труд по популяризации этой библиотеки среди широкого круга пользователей VBA путем разработки специализированных классов, реализующих интерфейсы к MPIR. Естественно, что любой теоретикочисловой алгоритм, реализованный на VBA, будет на порядки менее эффективен, что алгоритм из MPIR.
Владимир
 
 
 
#24
22.05.2018 16:40:45
sokol92, спасибо  вам за науку, а bedvit за очередную полезную разработку :oops:  :)
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
 
 
#25
22.05.2018 22:04:35
sokol92, благодарю за оценку моего проекта и понимании сколько трудов это стоило. Но не всем нужно столь точные вычисления. Это объективно. Сейчас пользуются не так много народа, но они есть и я этим вполне удовлетворен. Полученные знания и навыки тоже при мне. Двойная польза.
Jack Famous, пользуйтесь, познавайте, дерзайте....
Теперь по теме.
Дабы не быть голословным накидал две функции в Excel (C API). Результаты выкладываю.
Кому интересно - функция "PrimeInteger" определяет число простое/составное (60 знаков с легкостью) - пример в файле.
Другая "FactorizationInteger" - факторизация натурального числа, и поиск простых делителей натурального числа (поиск всех делителей в разработке) - знаков 30.

Работает все это очень просто.
Открываем библиотеку вашей разрядности Excel (просто щелкнув мышью) и файл пример "prime" - (этот файл нужен только для примера работы функций), библы работают без него, можете взять её с собой на другой комп, можно установить как надстройку (что бы каждый раз не открывать).

Да чуть не забыл - в библиотеках есть другие функции работы с длинными числами (вся арифметика) - все рабочие, можно тоже пользоваться.
Изменено: bedvit - 22.05.2018 22:09:57
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#26
22.05.2018 22:05:46
Для Excel x64 (2007 и выше). Делал быстро (как всегда по профилю - завал), поэтому в случае выявлении багов смело пишите (некоторый тестинг сделал, насколько позволяет время). Эти замечания относятся к стабильности работы. Арифметика должна быть верная, алгоритмы проверены приличным сроком использования.
Изменено: bedvit - 22.05.2018 22:13:26
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
#27
22.05.2018 22:46:42
Функции можно использовать и на VBA, через
Код
Application.Run
. sokol92, если вы пользуетесь COM, могу добавить и в методы класса целых чисел.
«Бритва Оккама» или «Принцип Калашникова»?
 
 
 
Страницы: 1
Наверх