User 14759433 Ответов: 2

Является ли этот код примером сита эратофена?


#include "bits stdc++.h"

using namespace std;
const int maxn=50000;

int fa[maxn],p[maxn];
int tst,ct,m,n;
int vi[101000];

void prep()
{
    ct=0;
    for( int i=2; i < maxn; i++ )
        if( ! fa[i] )
        {
            p[++ct]=i;
            for( int j=2; j <= (maxn-1)/i; j++ )
                fa[i*j]=i;
        }
}

void work()
{
    scanf( "%d%d", &m, &n );
    if( m == 1 )
        m++;
    int lim= (int)sqrt( n ) + 1;
    for( int i = 1; i <=ct; i++ )
    {
        if( p[i] > lim )
            break;
        int l = ( m - 1 ) / p[i] + 1;
        if( l == 1 )
            l++;
        int r = n / p[i];
        for( int j = l; j <= r; j++ )
            vi[ j * p[i] - m ] = tst;
    }
    for( int i = 0; i <= n - m; i++ )
    if( vi[i] != tst )
        printf( "%d\n", i + m );
}

int main()
{
    scanf( "%d", &tst );
    prep();
    while( tst )
    {
        work();
        tst--;
        if( tst )
            puts("");
    }
    return 0;
}


Что я уже пробовал:

Я пытаюсь узнать о сите эратофена и наткнулся на этот код, является ли это примером сита эратофена?

Patrice T

Код, который вы вставили, поврежден.

Rick York

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

2 Ответов

Рейтинг:
1

OriginalGriff

Попробуйте и посмотрите, что он делает.
Или... вернитесь туда, где вы его взяли, и спросите там.

Поиск случайных фрагментов программного обеспечения в интернете и вопрос "делает ли он это?" на совершенно другом сайте-это не очень хороший способ узнать: вместо этого, добравшись до Wiki, прочитайте статью о решето Эратосфена[^ и попробуй написать свою собственную. Таким образом, вы узнаете гораздо больше, поскольку люди учатся, делая, а не глядя на пример. Случайный фрагмент кода ничего не говорит вам о том, почему это так, какие альтернативы рассматривались, почему они были отброшены.

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


Рейтинг:
1

KarstenK

Ваш код плохо скопирован откуда-то и поэтому полон ошибок. Поищите в интернете какое-нибудь объяснение и какой-нибудь учебник, например Изучайте C++ чтобы научиться кодированию на C++.

Учитесь кодированию - это ваша домашняя работа.


Patrice T

- Ваш код плохо скопирован откуда-то и так полон ошибок."
поскольку я видел эту проблему много раз, я предполагаю, что существует комбинация
конкретный редактор/копирование > конкретный браузер/вставка
это испортило вставленный код.

KarstenK

Похоже, он исправил ошибку "плохой копии":- O