Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый алгоритм разложения числа на простые множители / 13 сообщений из 13, страница 1 из 1
01.10.2015, 17:34
    #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:44
    #39066399
RWolf
RWolf
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
гугли по ключевому слову "факторизация".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2015, 17:57
    #39066408
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
Число простое, если не делится без остатка на все простые меньше или равные корню этого числа.

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

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

Твой алгоритм "на глазок" содержит избыточные деления в том случае если аргумент A
будет изначально очень большим и простым числом.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.10.2015, 09:29
    #39066704
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
maytonТвой алгоритм "на глазок" содержит избыточные деления в том случае
У него и так до хрена будет лишних делений... нафига пробовать в качестве множителя все чётные, кроме двойки?
К тому же, если верхний предел аргумента = 2г, можно использовать статическую или предрасчитанную таблицу простых чисел до 45к.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.10.2015, 15:17
    #39067217
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
Кстати, как вы думаете, какая асимптотическая сложность у самого простого способа определения простоты числа n (проверка всех чисел до корня из n) ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.10.2015, 15:22
    #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:32
    #39067233
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
SashaMercuryКстати, как вы думаете, какая асимптотическая сложность у самого простого способа определения простоты числа n (проверка всех чисел до корня из n) ?
Насчёт сложности пока не скажу надо подумать. Но небольшое уточннение. Из личного наблюдения
и экспериментов. Определение простоты не всегда равно факторизации. Тоесть если тебе нужно
очень быстро с вероятностью 99.99.. доказать что число простое - используют другой метод.
Его используют на практике для генерации ключей ЕМНП в криптографии.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.10.2015, 04:13
    #39067502
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
maytonИз личного наблюдения
и экспериментов. Определение простоты не всегда равно факторизации.
равно факторизации только в том случае если n простое число, всё
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.10.2015, 14:23
    #39069431
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
ванмомас намбаванДело в том что я озадачен написанием намного быстрого алгоритма.Что бы он считал число 2*10^9 за 0.1сек.У кого ни будь есть алгоритмы на примете ?Можете поделится ? Тут обещают разложение чисел до 10^18 за одну миллисекунду :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.10.2015, 15:39
    #39069533
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
?ванмомас намбаванДело в том что я озадачен написанием намного быстрого алгоритма.Что бы он считал число 2*10^9 за 0.1сек.У кого ни будь есть алгоритмы на примете ?Можете поделится ? Тут обещают разложение чисел до 10^18 за одну миллисекунду :)
У тебя недостаточно знаний чтобы воплотить это решение. Разве что кто-то за тебя напишет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.10.2015, 16:04
    #39069569
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
mayton?пропущено...
Тут обещают разложение чисел до 10^18 за одну миллисекунду :)
У тебя недостаточно знаний чтобы воплотить это решение. Разве что кто-то за тебя напишет.Да ну. Там же написаноАлгоритм является чрезвычайно простым, красивым и эффективным.Так что ничего сложного
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.10.2015, 18:09
    #39069745
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Быстрый алгоритм разложения числа на простые множители
Мой месседж адресован к ванмомас намбаван
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Быстрый алгоритм разложения числа на простые множители / 13 сообщений из 13, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 495ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1340913]:
 0ms
get settings:
 10ms
get forum list:
 21ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 163ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 67ms
get tp. blocked users:
 2ms
others: 208ms
total:  495ms
x
x
Закрыть


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