UVA – 406 – Prime Cuts

  • Problem Statment : UVA – 406 – Prime Cuts
  • Type : Adhoc
  • Language : ANSI – C
  • Sol :
    • Used Sieve of Eratosthenes to generate primes, then determine the size of primes that will be outputted, then determine the start and the end from the equations below.
    • if the size of the input is larger than the no of collected then reset the start and the end pointers to the start and the end of the prime array.
#include <stdio.h>
#include <stdlib.h>
#define MAX 1003
int prime[MAX];
void sieve() {
	int i, p, c;
	for (i = 0; i < MAX; ++i) prime[i] = 1;
	for (p = 2; p < MAX; ++p) {
		if (prime[p])
			for (c = 2 * p; c < MAX; c += p)	prime[c] = 0;
	}
}

int main() {
	int i, N, C, A, B, K, S=0;
	sieve();
	while (scanf("%d %d", &N, &C) == 2 && !(S=0)) {
		int primes[MAX];
		for (i = 1; i <= N; i++)
			if (prime[i])	primes[S++] = i;

		K = 2 * C - (S % 2);
		A = K > S ? 0 : (S - K) / 2;
		B = K > S ? S : (A + K);

		printf("%d %d:", N, C);
		for (i = A; i < B; ++i)	printf(" %d", primes[i]);
		printf("\n\n");
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: