2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Нахождение простых чисел без деления
Сообщение02.07.2009, 15:11 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Предлагаю еще один способ нахождения простых чисел без деления.
Для наглядности буду записывать таблицей с комментариями.
В первом столбце будет проверяемое число, далее записываем остатки от деления на простые.
Пусть, к примеру, у нас есть два первых простых числа 2 и 3.

N P1 P2 P3 P4 P5 ......

3 1 0 Добавим 1 ко всем остаткам
4 0 1 Встретился 0, не простое
5 1 2 0 -нуля не было, отмечаем простое, добавляем столбец
6 0 0 1 - Где нули, там делится на 2 и 3, зато остаток 1 - на 5!
7 1 1 2 0 -нуля не было, добавляем столбец
8 0 2 3 1
9 1 0 4 2
10 0 1 0 3
11 1 2 1 4 0
12 0 0 2 5 1
13 1 1 3 6 2 0
14 0 2 4 0 3 1
15 1 0 0 1 4 2

Далее, думаю, понятно.
(По остаткам можно число вычислить по "китайской теореме об остатках.")

Подредактировал, обратите внимание, остатки для следующего числа вычисляются не делением, а добавлением единицы по модулю каждого найденного простого!
Сделал программу post231678.html#p231678

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 16:18 
Заслуженный участник


04/05/09
4582
iig в сообщении #226067 писал(а):
По остаткам число вычисляется по "китайской теореме об остатках."

Какое число? То, что слева? Это количество итераций, и считать его можно гораздо проще.
По сложности алгоритм хуже решета Эратосфена - $N log(N)$ vs $N log(log(N))$, элементарные операции сложнее, зато требует меньше памяти - $N/log(N)$ vs $N$.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 16:44 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Наверное, не надо было упоминать о китайской теореме, это другой вопрос.
А вот сложным алгоритм не считаю, по сравнению с решетом, конечно, сложнее,
зато быстрый и малоресурсный.
Это не надо сравнивать с решетом - здесь последовательное перечисление без деления.
Когда-то пытался сделать аналог решета - генератор тестируемых чисел на основе
уже известных простых, типа вначале нечетные, затем вида 6*к+-1 и т.д.
Кстати, в другой задаче, выкидывая по-другим правилам числа, обнаружилось, что оставшиеся можно найти как целая часть от нормальной функции.
Будет время - опубликую, интересно, хотя, как многое в математике, неприкладно.
На системе остаточных классов основаны многие быстрые алгоритмы,
например свертка в кольце многочленов.
Блейхут Р. Быстрые алгоритмы цифровой...М.,Мир, 1989

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 19:20 
Заслуженный участник


04/05/09
4582
Хм. Сложность алгоритма определяет скорость.
У решета количество итераций - $N log(log(N))$, где $N$ - максимальное искомое простое число, у вашего алгоритма - $N log(N)$ - значительно больше.
У вашего алгоритма есть ещё одно преимущество перед решетом, кроме размера памяти. Не надо заранее знать число $N$, можно увеличивать массивы динамически, и при остановке на любом числе $M$ потраченное время будет $M log(M)$.
Но выгодно это только если $M$ может быть сильно меньше $N$.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 19:46 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Считаю, все познается сравнением, т.е. коньюктурой.
Прелагаю желающим независимым протестировать и определить границы, где преобладает какой алгоритм.
Практическая польза - убедиться, что быстрые методы преобладают. Я уверен, что после сотен итераций скорость вычисления моего алгоритма превысит, а у решета память пойдет в опу.
Обещаю всяческую поддержку при одинаковых условиях.
Выбор оружия свой, но я бы хотел паскаль.

ЗЫ Найти число, когда будут различия и в какую сторону.

-- 02 июл 2009, 20:05 --

Пусть будет любой другой алгоритм для сравнения.
Могу сам побороться на ТрубеПаскуале.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 21:02 
Заслуженный участник


04/05/09
4582
А что, кроме как на опыте, вы не можете определить, что $N log(log(N))$ простых операций быстрее, чем $N log(N)$ сложных?

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 21:52 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
В принципе могу, только не пойму, что вы хотите и зачем.
Если вы такой корифей в быстрых методах, делайте, плз свой прогноз и посмотрим.
Да и воще, что от меня хотите, если только сегодня в в голову стукнуло!

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 21:56 
Заслуженный участник


04/05/09
4582
Всё оказалось гораздо хуже.
Я ошибся с оценкой сложности для вашего алгоритма, правильно будет $N^2/log(N)$.
Вот пример простейшего решета и вашего алгоритма:
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#define MAX_N 100000000

int P1, pp1[MAX_N];
bool xx1[MAX_N];

void make_primes1(int N)
{
    double time = gettime();
    P1 = 0;
    fill_n(xx1, N, 0);
    for ( int i = 2; i < N; ++i ) {
        if ( !xx1[i] ) {
            pp1[P1++] = i;
            for ( int j = i*2; j < N; j += i )
                xx1[j] = 1;
        }
    }
    time = gettime()-time;
    double t0 = time / (N*log(log(N)));
    cout << "P1="<<P1<<" time="<<time<<" t0="<<t0<<endl;
}

int P2, pp2[MAX_N], rr2[MAX_N];

void make_primes2(int N)
{
    double time = gettime();
    P2 = 0;
    for ( int i = 2; i < N; ++i ) {
        bool prime = true;
        for ( int j = 0; j < P2; ++j ) {
            if ( ++rr2[j] == pp2[j] ) {
                prime = false;
                rr2[j] = 0;
            }
        }
        if ( prime ) {
            pp2[P2] = i;
            rr2[P2] = 0;
            ++P2;
        }
    }
    time = gettime()-time;
    double t0 = time / (1/log(N)*N*N/2);
    cout << "P2="<<P2<<" time="<<time<<" t0="<<t0<<endl;
}

int main()
{
    make_primes1(100000);
    make_primes1(200000);
    make_primes2(100000);
    make_primes2(200000);
    return 0;
}
 

А вот результат:
Код:
P1=9592 time=0.000952887 t0=3.89973e-09
P1=17984 time=0.00189607 t0=3.78921e-09
P2=9592 time=0.759921 t0=1.74978e-09
P2=17984 time=2.4146 t0=1.47364e-09


-- Чт июл 02, 2009 14:57:50 --

iig в сообщении #226157 писал(а):
В принципе могу, только не пойму, что вы хотите и зачем.

Вы предложили на рассмотрение алгоритм.
Я оценил его скорость.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 22:03 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Смотрел вашу прогу, пока не врубился.
Беру таймаут
Постарайтесь найти во мне (алгоритме) хорошее,
обхаять кожный хочить
Могу свою прогу на паскале сделать,
согласен даже с вашей сыкушкой погоняться - настоящий мужук всех обгонит!

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 22:15 
Заслуженный участник


04/05/09
4582
MAX_N - предел для N, чтобы задать массивы.
N - максимальное число до которого искать простые числа.
make_primes1() - простейшее решето Эратосфена.
make_primes2() - предложенный здесь алгоритм.
P1, P2 - найденное количество простых чисел.
pp1[], pp2[] - массивы в которых функции сохраняют найденные простые числа.
xx1[] - массив для решета, если значение равно true, значит индекс - не простое число.
rr2[] - массив остатков для вашего алгоритма.

Программа находит простые числа до 100000 и до 200000 обоими алгоритмами и печатает затраченное время.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 22:44 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Делать свою прогу?
Вроде стало интересно, только не понял зачем.
Си у меня не установлен, сравнивать можно на других компутерах.
Может по ехе-сникам?

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 23:25 
Заслуженный участник


04/05/09
4582
iig в сообщении #226173 писал(а):
Делать свою прогу?
Вроде стало интересно, только не понял зачем.

А зачем тему начали?
В принципе, если вы согласны, что новый метод лишь на константу быстрее примитивного алгоритма с делением на все найденные простые числа, и ни в какое сравнение не идёт с более эффективными, например решетом Эратосфена, то обсуждение можно закончить.
У меня из ваших реплик сложилось впечатление, что вы не согласны.

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение02.07.2009, 23:59 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Удивляюсь, что вы не поняли, что мой алгоритм ничего общего не имеет с решетом. Там все что в решете отбирается, а тут все зернышки, что собрали перебираются!

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение03.07.2009, 00:04 
Заслуженный участник


04/05/09
4582
А что ещё приведённый алгоритм делает кроме поиска простых чисел?
В чём отличие от решета Эратосфена?

 Профиль  
                  
 
 Re: Нахождение простых чисел без деления
Сообщение03.07.2009, 00:07 
Заблокирован
Аватара пользователя


03/05/09

288
Gomel BY
Повторяю, это не решето, а сепаратор.
А что еще делать не знаю, только сегодня придумал, может интуиция еще что выдаст.
А в общем теория чисел хобби побоку, когда был студентом оттуда, зайдите на сайт поймете.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group