Нахождение простых чисел без деления

[iig]

Предлагаю еще один способ нахождения простых чисел без деления.
Для наглядности буду записывать таблицей с комментариями.
В первом столбце будет проверяемое число, далее записываем остатки от деления на простые.
Пусть, к примеру, у нас есть два первых простых числа 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

[venco]

iig в сообщении #226067 писал(а):

По остаткам число вычисляется по "китайской теореме об остатках."

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

[iig]

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

[venco]

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

[iig]

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

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

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

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

[venco]

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

[iig]

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

[venco]

Всё оказалось гораздо хуже.
Я ошибся с оценкой сложности для вашего алгоритма, правильно будет $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 писал(а):

В принципе могу, только не пойму, что вы хотите и зачем.

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

[iig]

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

[venco]

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

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

[iig]

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

[venco]

iig в сообщении #226173 писал(а):

Делать свою прогу?
Вроде стало интересно, только не понял зачем.

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

[iig]

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

[venco]

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

[iig]

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