Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Решето Эратосфена

Автор: ressac 2.11.2009, 11:43

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0

я вот сделал, только не очень мне нравится :(

может кто-то сможет более проще и элегантней написать это?

Код


void eratostenes(int,int[],int);
void mult(int,int,int[],int);

int main()
{
    int x;
    int N=20;
    int v[N];

    for (x=0; x<N; x++)
        v[x]=1;

    eratostenes(2,v,N);

    for (x=0; x<N; x++)
        printf("\n%3i <-> %i",x+1,v[x]);
}

void eratostenes(int pos, int v[], int N)
{
    if (pos*pos < N)
    {
        if (v[pos-1])
            mult(pos,pos,v,N);

        eratostenes(pos+1,v,N);
    }
}

void mult(int m, int pos, int v[], int N)
{
    if (pos < N)
    {
        if (v[pos])
        {
            int x = (pos+1)%m;
            if(!x)
                v[pos]= x;
        }

        mult(m,pos+1,v,N);
    }
}

Автор: 17dufa 2.11.2009, 12:50

ressac, Ваша функция mult слегка непонятна.
почему Вы не остановились на тупом переводе приведенного в вики псевдокода на си?

Автор: ressac 2.11.2009, 13:14

я просто сделал поиск методом деления.
вы думаете лучше сделать так как в вики? smile

попробую ща...

Автор: azesmcar 2.11.2009, 13:45

Код


#include <vector>
#include <iostream>
#include <functional>
#include <algorithm>

int main()
{
    const int n = 500;
    std::vector<int> arr(n, 0);

    int i = 1;
    for (std::vector<int>::iterator it = arr.begin(); it != arr.end(); ++it)
        *it = ++i;

    for (int p = 2; p <= n; ++p)
        for (int i = 2; i * p - 2 < n; ++i)
            arr[i * p - 2] = 0;

    std::remove_copy_if(
        arr.begin(),
        arr.end(),
        std::ostream_iterator<int>(std::cout, " "),
        std::bind1st(std::equal_to<unsigned int>(), 0));
}

так подойдет? хотя это не самое оптимальное решение.

Автор: ressac 2.11.2009, 13:53

там мне в рекурсивном виде надо ;)

Автор: ressac 2.11.2009, 14:32

вот я переделал mult

Код


void mult(int m, int pos, int v[], int N)
{
    if (pos*m <= N)
    {
        if(v[pos*m-1])
            v[ pos * m-1 ] = 0;

        mult(m+1,pos,v,N);
    }
}

Автор: 17dufa 2.11.2009, 15:33

ressac, усе, до меня дошло. На Вашем месте, я бы переделал mult вот в такое:

Код


void mult(int pos, int step, int v[], int N)
{
    if (pos <= N)
    {
        v[pos] = 0;
        mult(pos+step,v,N);
    }
}

и вызывал бы соответственно так:

Код


void eratostenes(int pos, int v[], int N)
{
    if (pos*pos < N)
    {
        if (v[pos-1])
            mult(pos*pos,pos,v,N);
        eratostenes(pos+1,v,N);
    }
}

Автор: ressac 2.11.2009, 16:49

ты опробывал у себя это? у меня виснит

Автор: 17dufa 3.11.2009, 11:02

ressac, нет конечно smile

начнем с того, что мой код просто в том виде, что здесь лежит не билдится))) я пытался задать направление. вот работающий код:

Код


void mult(int pos, int step, int v[], int N)
{
    if (pos <= N)
    {
        v[pos-1] = 0;
        mult(pos+step, step,v,N);
    }
}

void eratostenes(int pos, int v[], int N)
{
    if (pos*pos < N)
    {
        if (v[pos-1])
            mult(pos*pos,pos,v,N);
        eratostenes(pos+1,v,N);
    }
}

то есть в функции mult надо v[pos-1] = 0; а не v[pos] = 0.
С именами бы тоже чего-нить сделать не мешало.

а откуда такая любовь к рекурсии? на функциональный язык планируете перейти?

Автор: ressac 3.11.2009, 20:08

да нет просто это задачи из универа

а вообще рекурсия нравится сама по себе smile

Автор: 17dufa 5.11.2009, 10:56

ressac, главное не увлекайтесь. в C++ хвостовую рекурсию в цикл компилятор преобразовывать, насколько я знаю, не будет. в данной задаче, например, решение с циклами должно быть эффективнее и думаю многим, в частности мне, будет понятнее.
и имена все-таки поменяйте smile

Автор: Lazin 5.11.2009, 11:06

Код


#light
open System 
open Microsoft.FSharp.Collections

let primesUnderOneMillion = seq { 
    yield 2 
    let knownComposites = HashSet.Create()

    for i in 3 .. 2 .. int 1E6 do 
            
        let found = knownComposites.Contains(i) 
        if not found then 
            yield i 

        do for j in i .. i .. int 1E6 do 
               knownComposites.Add(j) |> ignore 
    } 

for x in primesUnderOneMillion do
    printfn "%d" x

Автор: 17dufa 5.11.2009, 12:27

Lazin, класс. а что за язык? и один косяк - автора интересует рекурсия. циклы ему не по душе smile

*а что делает |> ignore ? и внутренний цикл можно начинать не с i, а с i*i

Автор: Lazin 5.11.2009, 13:11

Цитата(17dufa @ 5.11.2009, 12:27

)

что за язык?

Цитата(17dufa @ 5.11.2009, 12:27

)

и один косяк - автора интересует рекурсия. циклы ему не по душе

согласен, но это и не цикл в традиционном понимании, это ленивая последовательность smile

Цитата(17dufa @ 5.11.2009, 12:27

)

а что делает |> ignore

оператор |> берет то, что справа и передает в ф-ю слева, в данном случае эта ф-я применяется для того, что-бы компилятор не ругался на игнорируемое возвращаемое значение

Цитата(17dufa @ 5.11.2009, 12:27

)

и внутренний цикл можно начинать не с i, а с i*i

нет, нельзя
допустим i = 3, тогда в хэш таблицу попадут числа начиная с 9, а нужно, что-бы попали - 3, 6, 9, 12 итд
угу, можно