UVa 406 Solution

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;

const int N = 1000;
bool sieve[N];

void eratosthenes() {
    // 0 和 1 是質數
    sieve[0] = true;
    sieve[1] = true;

    int sqrt_value = sqrt(N);

    // 找下一個未被刪掉的數字
    for (int i = 2; i <= sqrt_value; i++)
        if (!sieve[i]) {
            // k是倍數，j是質數i的倍數。
            // 由大到小判斷，當sieve[k]成立時，
            // k才能涵蓋所有「大於等於i的質數，其倍數」倍。
            for (int k = (N - 1) / i, j = i * k; k >= i; k--, j -= i)
                if (!sieve[k])
                    sieve[j] = true;
            // 運用小範圍的sieve[k]，避免存取大範圍的sieve[j],
            // 大幅減少cache miss。
        }


}

int main(int argc, char** argv){
    int iN, iC;
    
    eratosthenes();
    
    // 製作質數表
    vector<int> prime;
    for (int i = 1; i < N; i++) {
        if (!sieve[i])
            prime.push_back(i);
    }

    while(cin>>iN>>iC){
        //scanf("%d %d",&iN,&iC);
        printf("%d %d:",iN,iC);
        
        int doubleC = 2 * iC;
        int i,c;
        
        vector<int> output_prime;
  output_prime.clear();
        //get the primes < N
  output_prime.push_back(1);
        for(i=0;i<prime.size();i++){
            if(prime[i]<=iN) output_prime.push_back(prime[i]);
        }
        int index = output_prime.size();
        
        if (index % 2) {
            c = (iC * 2) - 1;
            i = (long) (ceil(index/2) - floor(c/2));
 
            if (i <= 0) {
                for (i = 0; i < index; i++)
                    printf(" %d", output_prime [i]);
            }
 
            else {
                while (i <= (ceil(index/2) + floor(c/2))) 
                    printf(" %d", output_prime [i++]);
            }
        }
 
        else {
            c = iC * 2;
            i = ((index/2)+1) - (c/2) - 1;
 
            if (i <= 0) {
                for (i = 0; i < index; i++)
                    printf(" %d", output_prime [i]);
            }
 
            else {
                while (i < ((index/2) + (c/2)))
                    printf(" %d", output_prime [i++]);
            }
        }
        printf ("\n\n");
    }
}