ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый алгоритм разложения числа на простые множители
13 сообщений из 13, страница 1 из 1
Быстрый алгоритм разложения числа на простые множители
    #39066385
Фотография ванмомас намбаван
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ванмомас намбаван
Участник
Решил написать задачу разложения числа на просты множители пример:16=2*2*2*2.В общем вышел следующий алгоритм.Думаю он стандартный и все хотя бы раз с ним сталкивались.
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
 static void OpenNum(int a)
        {
            int i = 2;
            while (i <= a)
            {
                if (a % i == 0)
                {
                    Console.Write(i);
                    a = a / i;
                    if (a > 1)
                    {
                        Console.Write('*');
                    }
                }
                else
                {
                    i++;
                }
            }
        }


Дело в том что я озадачен написанием намного быстрого алгоритма.Что бы он считал число 2*10^9 за 0.1сек.У кого ни будь есть алгоритмы на примете ?Можете поделится ?
...
Рейтинг: 0 / 0
01.10.2015, 17:34
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39066399
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RWolf
Участник
гугли по ключевому слову "факторизация".
...
Рейтинг: 0 / 0
01.10.2015, 17:44
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39066408
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Число простое, если не делится без остатка на все простые меньше или равные корню этого числа.

sqrt(2*10^9) = 44721 Можешь массивом забить. Можешь мой генератор взять
...
Рейтинг: 0 / 0
01.10.2015, 17:57
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39066460
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Добро пожаловать в клуб почитателей Миллера-Рабина, Эратосфена, Эвклида и Ландау.

Сабж называется как верно подметили - Факторизация.

Твой алгоритм "на глазок" содержит избыточные деления в том случае если аргумент A
будет изначально очень большим и простым числом.
...
Рейтинг: 0 / 0
01.10.2015, 19:29
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39066704
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
maytonТвой алгоритм "на глазок" содержит избыточные деления в том случае
У него и так до хрена будет лишних делений... нафига пробовать в качестве множителя все чётные, кроме двойки?
К тому же, если верхний предел аргумента = 2г, можно использовать статическую или предрасчитанную таблицу простых чисел до 45к.
...
Рейтинг: 0 / 0
02.10.2015, 09:29
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39067217
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Кстати, как вы думаете, какая асимптотическая сложность у самого простого способа определения простоты числа n (проверка всех чисел до корня из n) ?
...
Рейтинг: 0 / 0
02.10.2015, 15:17
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39067223
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
В принципе тут заменить
Код: sql
1.
while (i <= a)


на
Код: sql
1.
while (i*i <= a)


думаю достаточно для
ванмомас намбаванЧто бы он считал число 2*10^9 за 0.1сек.
...
Рейтинг: 0 / 0
02.10.2015, 15:22
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39067233
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryКстати, как вы думаете, какая асимптотическая сложность у самого простого способа определения простоты числа n (проверка всех чисел до корня из n) ?
Насчёт сложности пока не скажу надо подумать. Но небольшое уточннение. Из личного наблюдения
и экспериментов. Определение простоты не всегда равно факторизации. Тоесть если тебе нужно
очень быстро с вероятностью 99.99.. доказать что число простое - используют другой метод.
Его используют на практике для генерации ключей ЕМНП в криптографии.
...
Рейтинг: 0 / 0
02.10.2015, 15:32
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39067502
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonИз личного наблюдения
и экспериментов. Определение простоты не всегда равно факторизации.
равно факторизации только в том случае если n простое число, всё
...
Рейтинг: 0 / 0
03.10.2015, 04:13
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39069431
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
ванмомас намбаванДело в том что я озадачен написанием намного быстрого алгоритма.Что бы он считал число 2*10^9 за 0.1сек.У кого ни будь есть алгоритмы на примете ?Можете поделится ? Тут обещают разложение чисел до 10^18 за одну миллисекунду :)
...
Рейтинг: 0 / 0
06.10.2015, 14:23
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39069533
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
?ванмомас намбаванДело в том что я озадачен написанием намного быстрого алгоритма.Что бы он считал число 2*10^9 за 0.1сек.У кого ни будь есть алгоритмы на примете ?Можете поделится ? Тут обещают разложение чисел до 10^18 за одну миллисекунду :)
У тебя недостаточно знаний чтобы воплотить это решение. Разве что кто-то за тебя напишет.
...
Рейтинг: 0 / 0
06.10.2015, 15:39
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39069569
?
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
?
Гость
mayton?пропущено...
Тут обещают разложение чисел до 10^18 за одну миллисекунду :)
У тебя недостаточно знаний чтобы воплотить это решение. Разве что кто-то за тебя напишет.Да ну. Там же написаноАлгоритм является чрезвычайно простым, красивым и эффективным.Так что ничего сложного
...
Рейтинг: 0 / 0
06.10.2015, 16:04
| Ответить | Цитировать | Написать  
Быстрый алгоритм разложения числа на простые множители
    #39069745
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мой месседж адресован к ванмомас намбаван
...
Рейтинг: 0 / 0
06.10.2015, 18:09
| Ответить | Цитировать | Написать  
13 сообщений из 13, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый алгоритм разложения числа на простые множители
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=34&tid=1340913]:
 0ms
get settings:
 5ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 38ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 46ms
get tp. blocked users:
 1ms
others: 200ms
total:  323ms
созд. / загр.: 323ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]