Нахождение простых чисел. Оптимизация

[German Stimban]

Сообщение от Rooslan Khayrov

И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null.

Объяснил

Сообщение от German Stimban

что вывод данных на экран, запись данных в файл на диске занимают больше времени, чем процессорные операции.

Сообщение от Rooslan Khayrov

Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.

Гмм, попробовал то же самое на Мандриве, вариант с массивом работает медленнее. Попробовал на CentOS, вариант с массивом работает шустрее. Это становится интереснее.

[German Stimban]

Сообщение от Наташа

еще можно решето А́ткина глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю..

Наташа только что проводил эксперимент, сравнивал быстродействие двух алгоритмов:
Первый - берётся массив, первый элемент приравнивается двум. Далее в цикле проверяется делимость числа на элементы массива. Если число делится нацело, оно не простое, переходим к следущему. Если элемент массива больше квадратного корня из пробуемого числа, цикл прекращается. Если число простое, оно записывается в массив.
Второй - начальная стадия реализации решета Аткина. Оно выполняется в 2 раза дольше первого варианта.
То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.
Компилятор - GCC

[Shuhrat Ismailov]

Сообщение от German Stimban

То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.

Я, конечно, не спец в программировании, но имею очень хорошую методичку, которую когда-то рекомендовал студентам.
Там, кроме решета Аткина приведен метод индийского студента Сундарама

Вот что пишет автор:

Ещё одно интересное “решето” для нахождения простых чисел было предложено в 1934 году индийским математиком С. П. Сундарамом. Он придумал очень оригинальную таблицу, состоящую из бесконечного количества бесконечных арифметических прогрессий, причём каждый член первой прогрессии начинает новую прогрессию (с новой строки таблицы). Разностями прогрессий являются все нечётные числа, начиная с 3. (приведен рисунок)
Таблица бесконечно продолжается вправо и вниз. Разность арифметической прогрессии, записанной в первой строке таблицы, равна 3, разность арифметической прогрессии, записанной во второй строке таблицы, равна 5 и т. д. (все нечётные числа подряд являются разностями прогрессий).

Я реализовала метод Сундарама. Вот текст программы, написанный на языке QBASIC:
Программа для решета Сундарама
5 PRINT "VVEDITE M"
7 INPUT M
8 IF INT(M / 2) <> M / 2 THEN 5
9 IF M < 4 THEN 5
10 PRINT "VVEDITE L"
11 INPUT L
12 FOR I = M + 1 TO L STEP 2
15 B = I: A = (B - 1) / 2
17 C = A - 1
20 FOR N = 1 TO C
25 K = (A - N) / (1 + 2 * N)
30 IF INT(K) = K THEN 40
35 NEXT N
36 W = W + 1: PRINT "#"; W
37 PRINT B
40 NEXT I
45 PRINT
50 END
Программа работает очень просто. Надо ввести в программу чётное натуральное число M ≥ 4 и любое натуральное число L > M. Программа выдаст все простые числа в диапазоне от M+1 до L. Недостаток программы: при M = 4 теряются два простых числа: 2 и 3. Но этот недостаток очень легко устранить, если вставить в программу блок простой печати указанных простых чисел в случае, когда M = 4. По этой программе я получила следующий ряд простых чисел в интервале от 5 до 1000 (M = 4, L = 1000):
На форуме dxdy.ru по моей просьбе приведённая программа переписана на двух других языках программирования: Pascal и Turbo C++ 3.0. Вы можете посмотреть эти программы по следующей ссылке:

http://dxdy.ru/post218607.html?sid=6...9a8f9c#p218607

В моей реализации решета Сундарама использовано следующее утверждение:
Т Е О Р Е М А
Любое число A, находящееся в таблице Сундарама, может быть представлено в виде: A = (1 + 2 * N) * K + N,
где N – номер строки таблицы, в которой находится данное число, K – порядковый номер числа в этой строке.

[Наташа]

Сообщение от German Stimban

Наташа только что проводил эксперимент, сравнивал быстродействие двух алгоритмов: Первый - берётся массив, первый элемент приравнивается двум. Далее в цикле проверяется делимость числа на элементы массива. Если число делится нацело, оно не простое, переходим к следущему. Если элемент массива больше квадратного корня из пробуемого числа, цикл прекращается. Если число простое, оно записывается в массив. Второй - начальная стадия реализации решета Аткина. Оно выполняется в 2 раза дольше первого варианта.

Не очень поняла, что значит:

Сообщение от German Stimban

начальная стадия реализации решета Аткина.

Алгоритм он цельный

Сообщение от German Stimban

Оно выполняется в 2 раза дольше первого варианта.

Попробуйте элементарно увеличить максимальное число до 1 000 000, 10 000 000, 100 000 000, возможно получаться совершенно иные результаты

Сообщение от German Stimban

...для нахождения последовательности простых чисел оно не является наиболее оптимальным.

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

Сообщение от German Stimban

То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.

Честно говоря, я теряюсь в догадках -тот ли алгоритм Аткина /Эратосфена
тестируется ведь в этих алгоритмах ничего сказать о произвольном числе n нельзя пока не вычисляться все простые числа от 1 до n а для проверки на простоту произвольного числа существуют иные алгоритмы т.е. в результате в алгоритме Аткина как и Эратосфена мы должны банально получить все числа за 1 раз, а не проверять каждый раз по одному единственному числу

[Наташа]

Вот оно решето Аткина:

PHP код:

static public List<int> GetPrimNumbersAtkin(int num)
        {
            bool[] isPrimArr = new bool[num + 1];// Инициализация числового ряда
            double sqrt = Math.Sqrt(num);
            List<int> retList = new List<int>(); //Инициализация списка, простых чисел
            int n = 0;
            retList.Add(2);//2 и 3 сразу вносятся в список
            retList.Add(3);
            /*построение прямого произведения для всех чисел x и y
            от еденицы до квадратного корня из num */
            for (int x = 1; x <= sqrt; x++) 
                for (int y = 1; y <= sqrt; y++)
                {
                    n = 4 * x * x + y * y;
                    /* Здесь инвертируются решения для вышестоящего уравнения */
                    if (((n % 12 == 1) || (n % 12 == 5)) && (n <= num)) isPrimArr[n] = !isPrimArr[n];

                    n = 3 * x * x + y * y;
                    if ((n % 12 == 7) && (n <= num)) isPrimArr[n] = !isPrimArr[n];

                    n = 3 * x * x - y * y;
                    if ((x>y)&&(n % 12 == 11) && (n <= num)) isPrimArr[n] = !isPrimArr[n];
                }
            //теперь зачеркиваются все квадраты простых чисел и кратные им числа:
            for (int i = 5; i <= sqrt; i++)
                if (isPrimArr[i])
                    for (int k = 1; k*i*i <= num; k++)
                    {
                        isPrimArr[k * i * i] = false;
                    }
            //Возвращаться список простых чисел:
            for (int i = 5; i <= num; i++)
                if (isPrimArr[i]) retList.Add(i);
            return retList;
        } 


на c# -Сказочного увеличения производительности по сравнению с решетом Эратосфена не заметила...

[German Stimban]

Сообщение от Наташа

смысл алгоритма очень прост: ряд чисел 2,3,4,5,6,7,8,9,10...,n сначала находим первое не перечеркнутое число 2 и перечеркиваем все кратные ему числа 2,3,4,5,6,7,8,9,10..., ищем следующее не перечеркнутое число -в данном случае 3 и перечеркиваем дополнительно все кратные ему: 2,3,4,5,6,7,8,9,10..., теперь ищем следующее не перечеркнутое ит.д. пока не достигнем числа равного корню из n -все не зачеркнутые числа -простые -называеться алгоритм Решето Эратосфена

Ещё раз хочу сказать "спасибо", Вам, Наталья. Недавно с новой группой дошли до оптимизации алгоритмов и снова на примере простых чисел. В ходе урока раскачался и написал код решения с помощью решета Эратосфена на С++. (если интересно, могу вывести).
В результате максимально оптимизированный "классический" алгоритм

Сообщение от Rooslan Khayrov

Нет, просто перебирать делители только из уже найденных простых чисел.

искал значения от 1 до 5.000.000 за 5,83 секунд, а Ваш всего за 0,937

[Shuhrat Ismailov]

Решето Сундарама на турбо C++ 3.0

PHP код:

#include <iostream.h>

int main()
{
cout<<"Vvedite m: ";
int m;

cin>>m;
while((int(m/2)==m/2)&&(m>3))
   {
      cout<<"Vvedite L"<<endl;
      int l;
      cin>>l;
      if(l==0)break;//vihod
      double a,k=0.0,c;
      int b=0,w=0,t;
      for(int i=m+1;i<l;i+=2)
      {
         b=i;
         a=(b-1)/2;
         c=a-1;

         t=0;
         for(double n=1;n<c;n++)
         {

            k=(a-n)/(1+2*n);

            if(int(k)-k==0){t=1;break;}

         }

         if(t!=1)
         {
         w++;
         cout<<"#"<<" "<<w<<endl;
         cout<<b;
         }

      }
      cout<<endl;

   }

return 0;
} 


[Evgeniy Sklyarevskiy]

Сообщение от German Stimban

искал значения от 1 до 5.000.000 за 5,83 секунд,

Герман, найдите заодно, к чему стремится отношение количества простых чисел к количеству просмотренных чисел?

Еще зная, что вероятность того, два числа взаимно просты равна 6/pi^2 можно найти значение Пи! Об этом (и о простых числах) тута http://arbuz.uz/z_pi.html

И еще, раз уж занимаетесь глупостями, то они должны иметь красивый вид © :-0) Нарисуйте Скатерть Улама: все числа выписываются по расширяющейся спирали на клетчатой бумаге (отличное упражнение для новичков!), простые числа отмечаются ярким цветом. Потом смотрите на узор и фигеете! все разговоры о Боге просто отдыхают перед увиденным!

Я делал в древности на Фокспро в текстовом режиме в ДОСе и то впечатляло, попробуйте попиксельно, поглядим, как оно там все у Него устроено...

[German Stimban]

Сообщение от Evgeniy Sklyarevskiy

Еще зная, что вероятность того, два числа взаимно просты равна 6/pi^2 можно найти значение Пи!

Не совсем верно, ради разнообразия написал программку.

#include <iostream>
#include <stdlib.h>
#include <math.h>

unsigned long nod(unsigned long a,unsigned long b)
{
if (a<b)
{
unsigned long tmp=a;
a=b;
b=tmp;
}
if (a%b==0) return b;
else return nod(b,a%b);
}

int main()
{
std::cout<<"insert number of iterations: ";
unsigned long a,b,i=0,n,m=0;
std::cin>>n;
while (m++<n)
{
a=random();
b=random();
if (nod(a,b)==1) i++;
}
std::cout<<"Вероятность равна "<<double(i)/n<<"\n";
std::cout<<"Пи квадрат равен "<<6.0*n/i<<"\n";
std::cout<<"Пи равен "<<sqrt(6.0*n/i)<<"\n";
return 0;
}

Результат выполнения следующий (количество итераций - число pi):
100 - 2.94884
1 000 - 3.14918
10 000 - 3.14399
100 000 - 3.14037
1 000 000 - 3.14025
10 000 000 - 3.14142
100 000 000 - 3.1416
1 000 000 000 - 3.14164

[Evgeniy Sklyarevskiy]

Сообщение от German Stimban

Не совсем верно, ради разнообразия написал программку.

Классно! Спасибо! Почему не совсем верно, работает же, приближается к Пи, причем, то сверху то снизу сужаясь!!!!
Миллиард итераций дало три (почти четыре :-0) ) знака после запятой!

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

И напоминаю про Скатерть Улама, у кого есть время машинное!