Является ли этот код примером сита эратофена?
#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
Это пример довольно плохого кода, потому что в нем есть глобальные переменные длиной в один и два символа. Это очень, очень плохая практика. Я не вижу никакой необходимости в том, чтобы какая-либо из этих переменных была в первую очередь глобальной.