Это сложная проблема и одна из главных причин всех исследований квантовых компьютеров.Взгляните на алгоритм Шора .Простое перебор без оптимизации занял бы около 1000 лет, хотя в этом конкретном случае (64-разрядные целые числа) вы сможете сократить время выполнения до нескольких минут.
Предполагая, что у вас естьВ тривиальном случае (не более) одного большого простого множителя вы можете значительно ускорить процесс, например, сосчитав с 2 и попробовав каждое число (несколько раз, если это сработает; например, 12 будет равно 2, 2 и 3).После того, как вы найдете фактор, уменьшите число целей на этот коэффициент и проверьте, является ли новая цель простой.
Чтобы ускорить его, вы можете выполнять обработку в нескольких потоках, каждый из которых отвечает за диапазонделители.Вы можете запускать тестеры простоты в одном или нескольких потоках, предоставляя простые числа для потока тестирования, поэтому вы пытаетесь разделить только на простые числа.
Вы можете даже искать сверху вниз, если вы думаете, чточеловек, предоставляющий значение, пытается быть хитрым, хотя плотность простых чисел на нижнем конце намного выше, но это, скорее всего, не поможет.
Главное, однако, помнить, что наибольшее возможноефактор X, кроме самого X, является квадратным корнем из X. Каждый раз, когда вы находите фактор, максимально возможный оставшийся фактор значительно уменьшается.