Моё меню Общее меню Пользователи Правила форума Все прочитано
Вернуться   uForum.uz > ИКТ и телеком > IT-индустрия > Софт > Программирование
Знаете ли Вы, что ...
...до того как открыть новую тему, стоит использовать поиск: такая тема уже может существовать.
<< Предыдущий совет - Случайный совет - Следующий совет >>

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


Ответить

 
Опции темы Опции просмотра
Старый 28.12.2010 11:29   #11  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null.
Объяснил
Цитата:
Сообщение от German Stimban Посмотреть сообщение
что вывод данных на экран, запись данных в файл на диске занимают больше времени, чем процессорные операции.
Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.
Гмм, попробовал то же самое на Мандриве, вариант с массивом работает медленнее. Попробовал на CentOS, вариант с массивом работает шустрее. Это становится интереснее.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 28.12.2010 18:41   #12  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Наташа Посмотреть сообщение
еще можно решето А́ткина глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю..
Наташа только что проводил эксперимент, сравнивал быстродействие двух алгоритмов:
Первый - берётся массив, первый элемент приравнивается двум. Далее в цикле проверяется делимость числа на элементы массива. Если число делится нацело, оно не простое, переходим к следущему. Если элемент массива больше квадратного корня из пробуемого числа, цикл прекращается. Если число простое, оно записывается в массив.
Второй - начальная стадия реализации решета Аткина. Оно выполняется в 2 раза дольше первого варианта.
То есть, решето полезно, если мы хотим узнать является ли данное число простым, но для нахождения последовательности простых чисел оно не является наиболее оптимальным.
Компилятор - GCC
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 28.12.2010 22:13   #13  
Real ID Group uParty Member
Аватар для Shuhrat Ismailov
Оффлайн
Сообщений: 3,411
+ 2,928  2,654/1,361
– 84  129/82

UzbekistanОтправить сообщение для Shuhrat Ismailov с помощью Skype™Facebook
Цитата:
Сообщение от 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 – порядковый номер числа в этой строке.

Последний раз редактировалось Shuhrat Ismailov; 28.12.2010 в 22:21.
Ответить 
Старый 29.12.2010 00:43   #14  
Аватар для Наташа
Оффлайн
Сообщений: 1,306
+ 885  788/480
– 0  51/26

Germany
Цитата:
Сообщение от 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 раз, а не проверять каждый раз по одному единственному числу

Последний раз редактировалось Наташа; 29.12.2010 в 00:52.
Ответить 
Реклама и уведомления
Старый 29.12.2010 18:34   #15  
Аватар для Наташа
Оффлайн
Сообщений: 1,306
+ 885  788/480
– 0  51/26

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

                    
y;
                    if ((
12 == 7) && (<= num)) isPrimArr[n] = !isPrimArr[n];

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

Последний раз редактировалось Наташа; 29.12.2010 в 18:37.
Ответить 
Старый 06.05.2011 19:22   #16  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Наташа Посмотреть сообщение
смысл алгоритма очень прост: ряд чисел 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
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
"+" от:
Старый 06.05.2011 21:54   #17  
Real ID Group uParty Member
Аватар для Shuhrat Ismailov
Оффлайн
Сообщений: 3,411
+ 2,928  2,654/1,361
– 84  129/82

UzbekistanОтправить сообщение для Shuhrat Ismailov с помощью Skype™Facebook
Решето Сундарама на турбо 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;

__________________
http://www.matholymp.zn.uz
Ответить 
Старый 07.05.2011 00:40   #18  
Real ID Group Ultimate uParty Member ЕС
Аватар для Evgeniy Sklyarevskiy
Оффлайн
UZINFOCOM
Сотрудник ZiyoNET
AKA:ЕС, barbaris, arbuz
Сообщений: 32,709
+ 10,568  16,236/8,377
– 50  472/298

UzbekistanLiveJournalАккаунт на TwitterFacebook
Цитата:
Сообщение от German Stimban Посмотреть сообщение
искал значения от 1 до 5.000.000 за 5,83 секунд,
Герман, найдите заодно, к чему стремится отношение количества простых чисел к количеству просмотренных чисел?

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

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

Я делал в древности на Фокспро в текстовом режиме в ДОСе и то впечатляло, попробуйте попиксельно, поглядим, как оно там все у Него устроено...
Ответить 
Старый 10.05.2011 20:19   #19  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от 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
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 10.05.2011 23:45   #20  
Real ID Group Ultimate uParty Member ЕС
Аватар для Evgeniy Sklyarevskiy
Оффлайн
UZINFOCOM
Сотрудник ZiyoNET
AKA:ЕС, barbaris, arbuz
Сообщений: 32,709
+ 10,568  16,236/8,377
– 50  472/298

UzbekistanLiveJournalАккаунт на TwitterFacebook
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Не совсем верно, ради разнообразия написал программку.
Классно! Спасибо! Почему не совсем верно, работает же, приближается к Пи, причем, то сверху то снизу сужаясь!!!!
Миллиард итераций дало три (почти четыре :-0) ) знака после запятой!

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

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




Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Advertisement System V2.5 By Branden
OOO «Единый интегратор UZINFOCOM»


Новые 24 часа Кто на форуме Новички Поиск Кабинет Все прочитано Вверх