следующая тема »

[18 Апрель 2024, 09:19:36]

Новости, реклама:

[18 Апрель 2024, 09:19:36]

Новости, реклама:

[Toreador]

Итак, самый классный алгоритм для нахождения простых чисел? Хм?
Пока ещё не видел круче Эратосфена(до 255)...

_{Program Eratosfen;
Const N = 201;
{Возможно любое значение 1 < N < 256}
Var A, B: Set of 2 .. N;
    K, P: Integer;
Begin
    { Формирование исходного множества A;
    B - искомое множество простых чисел,
    сначала - пустое)
    A := [2 .. N]; B := [ ]; P := 2;
    Repeat
        {Поиск минимального числа в множестве A}
        while Not (p in A) do p := p+1;
        {Включение нацденного числа в множество B}
        b := b + [p];
        k := p;
        {Исключение из A чисел, кратных P}
        while k<=n do
        begin
            a := a - [k];
            k := k + p;
        end
    until a = [ ];
    { Вывод результата, т.е. всех чисел из множества B
    в порядке возрастания}
    for p := 2 to n do if p in b then writeln(p)
end.}

Может кто предложит круче?!

[maxposedon]

гы-гы-гы )
прежде чем мерятся, доставай всё © кто-то

а теперь покажи всем свой алгоритм для чисел > 256, а?))
а то до 256 простые числа и константами забить можно,
или по твоему простых чисел > 256 не бывает, или они никаму не нужны?

вот так и появляются Горе-паскаль-программисты...
а пока (на правах рекламы)

max_posedon@Melnikov temp % cat ./prime.rb
#!/usr/bin/ruby

require 'mathn'

Prime.new.each do |prime|
        break if prime > 1000
        p prime
end

P.S.
2Tareador, лучше не позорься, а пиши/выкладывай код на C/C++, хоть кoму-то польза будет

[7floor]

maxposedon, и чем ты понтанулся? Алгоритм напиши, а не покажи, что умеешь заюзать готовое. А то, ИМХО, сел в лужу.

[maxposedon]

maxposedon, и чем ты понтанулся? Алгоритм напиши, а не покажи, что умеешь заюзать готовое. А то, ИМХО, сел в лужу.

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

хотя, сча навояемс...

[maxposedon]

max_posedon@Melnikov ~ % cat prime.cpp
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

const int val = 1000;

int main()
{
        // primes хранит простые числа
        vector<int> primes;

        // пробегаем диапазон
        for(int i=2; i<val; i++)
        {
                //проверяем просто ли очередное число
                bool prime = true;
                int  sqrt_i= (int)sqrt(i)+1;

                //пытаемся делить на все простые числа, до корня из i
                for(unsigned int j=0; j<primes.size(); j++)
                        if (i%primes[j]==0)
                        {
                                prime = false;
                                break;
                        }
                        else if (primes[j] >= sqrt_i)
                                break;
                //если простое, то заносим
                if (prime)
                        primes.push_back(i);
        }

        //вывод
        for(unsigned int i=0; i<primes.size(); i++)
                cout << primes << " ";
        cout << endl;

        return 0;
}

ну дабы, не было это просто так...
у моего Алгоритма сложность O(N*log(M)),
N - кол-во чисел
M - кол-во простых чисел

для проверки на простоту проверяется все до N, а тока простые и то до корня из числа
поэтому и получаем N*log(M)

[VooDoo]

гы, знакомое дело. Кстати когда-то задача была на районной олимпиаде. Были очень большие числа, маленькое время и тихоходный комп.
Кстати, ходить можно через одно, зачем проверять чётные...
а что именно писал уже не помню

[maxposedon]

Кстати, ходить можно через одно, зачем проверять чётные...

тут шутка в чем, O(N/2*log(M)) == O(N*log(M)) )

ведь при чётных внутренний цикл, не цикл собственно
т.е. если ити тока по четным, ускорение составит ~1-5% в зависимости от val (при больших val, `ускорение` уменьшается)... хотя запихнуть в primes 2 и ити нечётным, наверное действительно `кошернее`

[VooDoo]

просто в форе сделать (int i=3; i<val; i+=2)
а в праймс не надо пихать, если только в конце
всё-таки при больших числах мы будем каждый раз делать ненужную работу. Может секунды, но приятно

[VooDoo]

на джаве :

    int n=100000000;

Started at ->Mon Nov 20 16:53:16 EET 2006
Finish time ->Mon Nov 20 16:57:44 EET 2006
5761454  и плюс 1 и 2 итого 5761456

[maxposedon]

такс, провёл замеры, с выводом всех ~5млн чисел на экран и без)
(просто вывод это достаточно долго, а из поста VooDoo, я не понял как он запускал)
код (что выше, и с модификацией про нечётность)
компилировался g++ -O3 prime.cpp,
вывод производился на konsole
(такс-у не удалось загрузить проц на 100% из-за всяких там beryl-ов/amarok-ов и прочим)

1. оригинальный, время засекалось с выводом
./a.out  113,96s user 0,62s system 60% cpu 3:09,42 total
2. без вывода
./a.out  112,36s user 0,15s system 76% cpu 2:27,34 total
3. пробег тока по нечетным, с выводом
./a.out  111,49s user 0,83s system 65% cpu 2:52,45 total
4. нечетные, без вывода
./a.out  108,05s user 0,14s system 75% cpu 2:23,24 total


2VooDoo , обрати внимание `оптимизация по нечетным` лежит в границах статистической погрешности ..

такс... кажется мы о чем-то/ком-то забыли
2Tareador, а теперь ваш код, и замеры ) ждемс...

[VooDoo]

у меня был без вывода, без чётных. много времени жрёт вывод:(
и надо немножко переделать, завтра выложу. и хочу попробовать на руби, что будет быстрее.
Кстати для паскаля, если мне не изменяет память была директива {R-} выключала range check для массива. Очень ускоряла работу с массивами. Это аффтару на заметку

[maxposedon]

ruby сильно сплющит от такого кол-ва объектов, причем полноценных объектов... (`число-дробилки` не его сильная сторона)
хотя реализация достаточно красивая будет

max_posedon@Melnikov temp % cat primes.rb
#!/usr/bin/ruby

val = 10000
primes = [2]

3.step(val,2) do |i|
        sqrt_i = i ** 0.5 + 1
        primes << i if !primes.find{ |j| (i%j == 0) || (break if j > sqrt_i) }
end

p primes

[VooDoo]

и джаву расплющило. Отдал ей гиг мозгов, оставил на ночь... Когда пришёл увидел out of memory
Да, итераторы в руби очень приятная вещь

[maxposedon]

и джаву расплющило. Отдал ей гиг мозгов, оставил на ночь... Когда пришёл увидел out of memory
Да, итераторы в руби очень приятная вещь

2VooDoo , покажи таки Java-код (для меня - чисто посмеятся с языка )
и я не понял, при каких N расплющело то?
естественно код должен, создавать массив простых...

[Toreador]

гы-гы-гы )
прежде чем мерятся, доставай всё © кто-то
P.S.
2Tareador, лучше не позорься, а пиши/выкладывай код на C/C++, хоть кoму-то польза будет

Да-да-да... началось... ну как же тут без споров какой язык круче?! А?
Простой вопрос для тебя: Ты название темы читал, когда заходил и оставлял месаги?
На счёт позориться, не знаю, это не тебе решать...
(Может ты сразу с детства, уже в утробе матери, знал С/С++?)
Ладно, кароче... чё то нет нормальных программистов у нас в Гродно :-?...
...

[VooDoo]

чё то нет нормальных программистов у нас в Гродно

эт ты зря, по крайней мере они были...
2Max : после некоторых оптимизаций получилось такое:
 int n=100000000;

        System.out.println(n);
        System.out.println("Started at ->"+new Date());
        ArrayList primes= new ArrayList();
        primes.add(new Integer(3));
        int i_sqrt;
        int k=0;
         Integer subList[]=null;
        loop:for (int i=5 ; i < n ; i += 2)
        {

            i_sqrt=(int)Math.sqrt(i);
            if (((Integer)primes.get(k)).intValue()<=(i_sqrt))
            {
             k++;
             subList = (Integer[])primes.subList(0,k).toArray(new Integer[k]);
            }

            for (int j = 0; j< k ;j++)
            {
                if (i%(subList[j]).intValue()==0)
                {
                    continue loop;
                }
            }
                        primes.add(new Integer(i));
        }

        System.out.println("Finish time ->"+new Date());
        System.out.println(primes.size());        
        }

скажу сразу, тут я вырезал кусок из ArrayList и вставлял в простой массив, так получается дешевле в два раза(всё таки массивы быстрее всего:) ) в итоге:
100000000
Started at ->Tue Nov 21 14:36:45 EET 2006
Finish time ->Tue Nov 21 14:38:36 EET 2006
5761454
время почти как сишное

[VooDoo]

расплющило его на 1000000000

Toreador ждём примеров на паскале и результатов. Уж больно интересно:)

[maxposedon]

Да-да-да... началось... ну как же тут без споров какой язык круче?! А?
Простой вопрос для тебя: Ты название темы читал, когда заходил и оставлял месаги?
На счёт позориться, не знаю, это не тебе решать...
(Может ты сразу с детства, уже в утробе матери, знал С/С++?)
Ладно, кароче... чё то нет нормальных программистов у нас в Гродно :-?...
...

1. споров тут нет, тут пока тока алгоритмы и код, мы ждем код от тебя...
2. да читал, паскаль далеко не рулез - раз, ты все таки хотел больше про алгоритмы - это два
3. решать не мне, а дать совет я думаю я могу)
4. нет программистов? гы-гы, а ты про всех программистов в Гродно что-то знаешь?)

ну и вообще говоря всё это мелочи, мы ждем от тебя код,
и дело наверное таже не в скорости, а в лаконичности и удобночитаемости

[Toreador]

Toreador ждём примеров на паскале и результатов. Уж больно интересно:)

1. споров тут нет, тут пока тока алгоритмы и код, мы ждем код от тебя...
ну и вообще говоря всё это мелочи, мы ждем от тебя код,
и дело наверное таже не в скорости, а в лаконичности и удобночитаемости

От меня? хм...  
И чего вы ожидаете?
Супер-мега кода... Нет ребята, Паскаль - это "начальный" язык. С него начинают практически все программисты... Ведь в основном суть то не втом какой язык круче, а в том как ты умеешь его использовать, вернее писать на нём массивные проги...
Превращать идею в алгоритм, а потом в программу...
Ладно вот вам простенький алгоритм нахождения простых чисел >255...

var
  a:array[1..32000] of integer;
  n,p,i,j,k:longint;

function prost(n:longint): boolean;
 var i,j:longint;
  begin
   j:=0;
 for i:=1 to n do
   if n mod i = 0 then j:=j+1;
     if j=2 then begin prost:=true; a:=n; end else prost:=false;
end;

 begin
  write('Vvedi granicu diapazona: '); readln(k);
for n:=1 to k do begin
    p:=n+1;
    while not prost(p) do p:=p+1;
  end;
a[1]:=1;
 for i:=1 to n do if (a<>0) then write(a:5);
end.

Можно усовершенствовать, упростить, но делал на скорую руку...
Теперь можете критиковать!........

[Toreador]

Ладно... фиг с ним...
Алгоритм есть... вроде есть... поехали дальше...
 
Всегда сложность составляют в олимпиадных задачах графы...
Ладно пойду поищу нормальную задачу на кротчайшие пути и т.п....

[VooDoo]

так сколько времени твой алгоритм будет считать при n=100000000?

[maxposedon]

так сколько времени твой алгоритм будет считать при n=100000000?

а самому посчитать?)

у него следующий алгоритм (своё `крутое` решето эратосфера он решил не реализовывать)
каждое число(n) из диапозона 1 .. k, он делит на _все_ числа из диапозона 1..n, и убеждается что делителей ровно 2.

итого делаем выводы
1. алгоритм жутко убогий, и даже этот простейший алгоритм он ужасно реализовал
2. сложность алгоритма O(N*N) сл-но...
при N=100млн =10^8, у него будет 10^16 операций на процессоре в 1Ghz это займет примерно
10^5 секунд = 1666мин = 27часов = 1сутки , т.е. это займет несколько суток

2Toreador почитай хоть котова чтоли, а то тебе явно ничего не светит

[VooDoo]

10^16 операций на процессоре в 1Ghz

что-то слишком много. Для пня 4  можно считать примерно 1 к 1(Ghz vs. GFLOPS) и то... я бы сказал меньше, но на самом деле от задачи зависит.

А с Котова надо начинать...

[maxposedon]

10^16 операций на процессоре в 1Ghz

что-то слишком много. Для пня 4  можно считать примерно 1 к 1(Ghz vs. GFLOPS) и то... я бы сказал меньше, но на самом деле от задачи зависит.

может я непонятно сформулировал, я считал скока (O-большое) будет выполнятся 10^16 операций (у него N*N сложность) на 1Ghz -проце(O(10^9)-операций в секунду), получилось O(сутки) посчитал вроде правильно

[VooDoo]

ну да, сформулировал совсем не понятно.
брррр 10^16 делим на 10^9 = 10^7.
2777 часов = 115 суток

[maxposedon]

ну да, сформулировал совсем не понятно.
брррр 10^16 делим на 10^9 = 10^7.
2777 часов = 115 суток

каюсь, обсчитался в 100раз)...

я тут вспомнил одно выскаывание:
Данный процесс будет длится 10^(10^10), вот тока я не помню, толи секунд, толи лет, что в принципе при таких числах не имеет значения © препод по физике

[Toreador]

Да ну Вас критики...
Ща почитаю...

[Toreador]

Спасибо чуваки... Чутарик меня разозлили...
Правда Котов не помог , но сам допетрил вот до этого алгоритма :

var n,p,i,j,k:longint;
 procedure prost;
  begin j:=0;
 for i:=1 to n do begin
  if n mod i = 0 then j:=j+1;
  if j>2 then break;
 end;
  if j=2 then write(i:10);
end;
 begin
  write('Vvedi granicu diapazona: '); readln(k);
for n:=1 to k do prost;
readln;
end.


Критикуйте, если есть что???!!!!

И вот вам интересная олимпиадная задачка:
 «Интернет–магазин».
Входной файл:       shop.in
Выходной файл:       shop.out
В базе данных (далее – БД) Интернет–магазина содержится информация о K приобретенных товарах. Злоумышленник, взломав БД, получил возможность поменять местами между собой:
•      содержимое полей с данными о цене товаров;
•      содержимое полей с данными о количестве приобретенных единиц товара.
В результате этих действий Интернет–магазин может понести убыток по общей стоимости товаров, который определяется разностью между исходной стоимостью приобретенных товаров в неповрежденной БД и их стоимостью после действий злоумышленника.
Определить наибольший убыток по общей стоимости товаров, который может принести злоумышленник владельцам магазина.
Формат входных данных.
Входной файл shop.in содержит К+1 строк. В первой строке находится число K. В каждой из остальных K строк записаны два действительных числа a и b – соответственно цена за единицу и количество приобретенного товара до действий злоумышленника.
Ограничения.
1 ? K ? 1000
0.00 < a ? 1000000.00
0.00 < b ? 1000000.00
Числа a и b содержат не более двух разрядов после десятичной точки.
Формат выходных данных:
Выходной файл shop.out должен содержать одну строку с искомым количеством убытка по общей стоимости товаров с точностью до четырех разрядов после десятичной точки.

Пример файла входных данных:
4
2 2.5
3.5 4
1 2
2.5 5

Пример файла выходных данных (для приведенного выше входного файла):
7.2500

[VooDoo]

да не надо цикл делать до n. как минимум n/2. больше же чем на n/2 n не разделится.

задачку потом посмотрим

[maxposedon]

Правда Котов не помог , но сам допетрил вот до этого алгоритма :

var n,p,i,j,k:longint;
 procedure prost;
  begin j:=0;
 for i:=1 to n do begin
  if n mod i = 0 then j:=j+1;
  if j>2 then break;
 end;
  if j=2 then write(i:10);
end;
 begin
  write('Vvedi granicu diapazona: '); readln(k);
for n:=1 to k do prost;
readln;
end.


Критикуйте, если есть что???!!!!

а!!!...
во первых, алгоритм остался  почти тот же, реализация тока лучше

вот если заменить, проверку, вместо n, до sqrt(n)... и бежать от 2(а не от 1)
и выход не при j>2, а при j>0 то уже лучше...
НО! сложность будет N*log(N), что правда уже неплохо)), но сё равно в раз 100 медленнее чем у меня,
(хотя уже тот факт что 100 это константа , радует)

а сл-но опять N*N, и опять ~115 суток при n = 10^8

ты бы думалку включил)
вперед читать основы, и попроси своих преподов расказть тебе про сложность алгоритмов, а то умрёшь в неведении...
рано тебе еще задачи на графы решать)

а мы посмотрим...