(Relax 数论1.11)POJ 1595 Prime Cuts(欧拉筛法: 输出1~n区间中中间的2C个素数)

 
#include   
#include   
#include   
#include   
/** 
 * 2 2 3 17 
 2 2 3 29 

 2 2 5 37 
 */  
using namespace std;  
  
const int maxn = 100002;//不要开得太大,否则可能MLE  
int su[maxn];  
bool u[maxn];  
int num = 0;  
  
void prepare() {  
    int i, j;  
    memset(u, true, sizeof(u));  
  
    for (i = 2; i <= 100001; ++i) {  
        if (u[i]) {  
            su[++num] = i;  
        }  
  
        for (j = 1; j <= num; ++j) {  
            if (i * su[j] > 100001) {  
                break;  
            }  
  
            u[i * su[j]] = false;  
  
            if (i % su[j] == 0) {  
                break;  
            }  
        }  
    }  
}  
  
int main() {  
    prepare();  
  
    int n, c;  
    int pri[maxn];  
    while (scanf("%d%d", &n, &c) != EOF) {  
        int i;  
        int j = 1;  
        memset(pri, 0, sizeof(pri));  
  
        for (i = 1; i <= n; ++i) {  
            if (u[i]) {  
                pri[j++] = i;  
            }  
        }  
  
        printf("%d %d:",n,c);  
  
        int nm = 0;  
        if (c * 2 > j) {//如果要求输出的素数的个数>





[1,n]内所拥有的素数的个数  
            for (i = 1; i < j; ++i) {//全部输出  
                printf(" %d", pri[i]);  
            }  
            printf("\n\n");  
        } else {//****否则根据要求输出中间的规定个数的素数  
            if (j % 2 == 0) {  
  
                int pos = (j - 2 * c) / 2;//打印中间的2C-1个元素  
  
                for (i = pos + 1;; ++i) {  
                    nm++;  
                    if (nm > (2 * c - 1)) {  
                        break;  
                    }  
  
                    if (pri[i] != 0) {//**这个判断其实可以没有....  
                        printf(" %d", pri[i]);  
                    }  
                }  
                printf("\n\n");  
            } else {  
                int pos = (j - 2 * c) / 2;  
                for (i = pos + 1;; ++i) {  
                    nm++;  
                    if (nm > (2 * c)) {  
                        break;  
                    }  
  
                    if (pri[i] != 0) {  
                        printf(" %d", pri[i]);  
                    }  
                }  
  
                printf("\n\n");  
            }  
        }  
    }  
  
    return 0;  
}