Факторизация чисел <=1*10^9 быстрее, чем за 1 секунду

12.06.2014, 23:34. Показов 937. Ответов 0

Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам

В общем - сабж
Есть два числа n и m
Вот мой алгоритм факторизации (попутно засовывая их в массивы)

Pascal
1
2
3
4
5
6
7
8
9
10
j:=1;
i:=2;
k:=1;
while ((n<>1) or (m<>1) )   do 
  begin
   1:
    if n mod i = 0 then begin a[j]:=i; inc(j); n:=n div i; goto 1;  end;
    if m mod i = 0 then begin b[k]:=i; inc(k); m:=m div i; goto 1;  end;
    inc(i);
  end;

Где i - число, на которое будем делить, j - индекс массива 1, k - соответственно, второго.
На a c m p выдает TLE при требованиях n,m <=1*10^9.
Прошу помочь составить какой-то более эффективный алгоритм. (пробовал и с sqrt(n) - Тот же TLE).

Пы.Сы - кому интересно - задача 651

Добавлено через 58 минут
Бамп.
За одно обновлю.
Алгоритм выходит за рамки времени, когда одно из чисел является простым, да еще и очень большим. Тобишь нужно очень много операций. Как от этого избавиться?

Заказать работу у эксперта

IT_Exp

Эксперт

34794 / 4073 / 2104

Регистрация: 17.06.2006

Сообщений: 32,602

Блог

12.06.2014, 23:34

Ответы с готовыми решениями:

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

C# работает быстрее чем С++
имеется файл типа 6 1.0 2.0 3.0 4 5 6 7 1.0 2.0 3.0 4 5 6 7 1.0 2.0 3.0 4 5 6 7 1.0 2.0 3.0 4 5 6 7 1.0 2.0 3.0 4 5 6 7 1.0...

Быстрее чем цикл
Доброго времени уток дорогие форумчане. Интересует вот какая штуковина, допусти есть программа которая открывает два файла, смотрит на...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

BasicMan

Эксперт

29316 / 5623 / 2384

Регистрация: 17.02.2009

Сообщений: 30,364

Блог

12.06.2014, 23:34

Помогаю со студенческими работами здесь

Что и в чем быстрее?
Разъясните пожалуйста: в чем разница в скорости в ArrayList and LinkedList? А также в HashMap and LinkedHashMap? В ArrayList быстрее...

Чем парсить HTML быстрее?
Посоветуйте - чем парсить HTML быстрее всего? Использую HtmlAgilityPack, мой код парсит 12 страниц за 15+ сек static string...

Правда что С быстрее чем С++?
Имеется в виду на исполнении, а не на момент компиляции... Наверняка такая тема уже была, но я не нашёл, если дадите ссылку также буду...

C программа компилируется быстрее чем C++
Почему программа на C компилируется быстрее чем на С++?

Sin быстрее чем из math.h
ребят, вообщем мне задали написать программу которая считала синус быстрее чем из math.h ) скорость должна достигаться путем потери...

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:

Опции темы

Новые блоги и статьи Все статьи Все блоги /
Batch Transform и Batch Gizmo Drawing API в Unity GameUnited 20.04.2025 В мире разработки игр и приложений на Unity производительность всегда была критическим фактором успеха. Создатели игр постоянно балансируют между визуальной привлекательностью и плавностью работы. . .	Звук в Unity: Рандомизация с Audio Random Container GameUnited 20.04.2025 В современных играх звуковое оформление часто становится элементом, который либо полностью погружает игрока в виртуальный мир, либо разрушает атмосферу за считанные минуты. Представьте: вы исследуете. . .	Максимальная производительность C#: Советы, тестирование и заключение stackOverflow 20.04.2025 Погружение в мир микрооптимизаций C# открывает перед разработчиком целый арсенал мощных техник. Но как определить, где и когда их применять? Ответ начинается с точных измерений и профилирования. . . .	Максимальная производительность C#: Предсказание ветвлений stackOverflow 20.04.2025 Третий ключевой аспект низкоуровневой оптимизации — предсказание ветвлений. Эта тема менее известна среди разработчиков, но её влияние на производительность может быть колоссальным. Чтобы понять. . .	Максимальная производительность C#: Векторизация (SIMD) stackOverflow 20.04.2025 Помимо работы с кэшем, другим ключевым аспектом низкоуровневой оптимизации является векторизация вычислений. SIMD (Single Instruction, Multiple Data) позволяет обрабатывать несколько элементов данных. . .
Максимальная производительность C#: Процессорный кэш stackOverflow 20.04.2025 Знакомство с внутренним устройством процессорного кэша — ключевой шаг в написании по-настоящему быстрого кода на C#. Этот слой архитектуры компьютера часто ускользает от внимания разработчиков, но. . .	Максимальная производительность C#: Введение в микрооптимизации stackOverflow 20.04.2025 В мире разработки на C# многие привыкли полагаться на . NET Runtime, который "магическим образом" сам оптимизирует код. И часто это работает - современные JIT-компиляторы творят чудеса. Но когда речь. . .	MVC фреймворк в PHP Jason-Webb 19.04.2025 Архитектурный паттерн Model-View-Controller (MVC) – это не просто модный термин из мира веб-разработки. Для PHP-программистов это фундаментальный подход к организации кода, который радикально меняет. . .	Dictionary Comprehensions в Python py-thonny 19.04.2025 Python славится своей выразительностью и лаконичностью, что позволяет писать чистый и понятный код. Среди множества синтаксических конструкций языка особое место занимают словарные включения. . .	Шаблоны и протоколы для создания устойчивых микросервисов ArchitectMsa 19.04.2025 Микросервисы — архитектурный подход, разбивающий сложные приложения на небольшие, независимые компоненты. Вместо монолитного гиганта, система превращается в созвездие небольших взаимодействующих. . .

Наверх