UVa 10871 - Primed Subsequence

// UVa 10871 - Primed Subsequence

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int p;
int prime[10001];
bool isprime[10001];

bool primed(int x) {
	if (x < 10001)
		return isprime[x];
	else {
		for (int i = 0; i < p; i++)
			if (x % prime[i] == 0)
				return false;
		return true;
	}
}

int main() {
	// sieve
	memset(isprime, true, sizeof(isprime));
	for (int i = 4; i <= 10000; i += 2)
		isprime[i] = false;
	p = 1;
	prime[0] = 2;
	for (int i = 3; i < 10001; i += 2)
		if (isprime[i]) {
			prime[p++] = i;
			for (int j = i * i; j <= 10000; j += (i << 1))
				isprime[j] = false;
		}
	//
	int t;
	for (cin >> t; t; t--) {
		// input
		int n;
		cin >> n;
		int b[10001], a[10001];
		b[0] = 0;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			b[i] = b[i - 1] + a[i];
		}
		// find
		int s1, s2;
		bool found = false;
		for (int j = 1; j < n; j++) {
			for (int i = 1; i <= n - j; i++) {
				if (primed(b[i + j] - b[i - 1])) {
					s1 = i;
					s2 = i + j;
					found = true;
					break;
				}
			}
			if (found)
				break;
		}
		// output
		if (!found)
			printf("This sequence is anti-primed.\n");
		else {
			printf("Shortest primed subsequence is length %d:", s2 - s1 + 1);
			for (int i = s1; i <= s2; i++)
				cout << " " << a[i];
			cout << endl;
		}
	}
	return 0;
}