uva 406 - Prime Cuts

Types: Number theory, primes number, sieve...

Problem link

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 1010;
//------------------------------------
int a[maxn];
bool isPrime[maxn];
int n,c;
//------------------------------------
void sieve() {
 memset(isPrime,true,sizeof(isPrime));
 int i,j;
 i=2;
 while (i<=int(sqrt(1000))) {
  if (isPrime[i]) 
  {
   j=i+i;
   while (j<=1000) 
   {
    isPrime[j]=false;
    j=j+i;
   }
  }
  i++;
 }
}
//------------------------------------
void solve(int n, int c) {
 int cnt = 0;
 for (int i=1; i<=n; i++)
  if (isPrime[i]) a[++cnt]=i;
 if (cnt%2==0) c*=2; 
 else c=c*2-1;
 int tmp;
 if (c<cnt) tmp = (cnt-c)/2;
 else 
 {
  tmp = 0;
  c = cnt;
 }
 
 for (int i=tmp+1; i<=tmp+c; i++) 
  if (i<tmp+c) cout << a[i] << " ";
  else cout << a[i];
}
//------------------------------------
int main() {
 sieve();
 while (!cin.eof())
 {
  cin >> n >> c;
  if (cin.eof()) break;
  printf("%d %d: ",n,c);
  solve(n,c);
  cout << endl;
  cout << endl;
 }
 return 0;
}
//------------------------------------