/*
* UVA_10871.cpp
*
* Created on: 2013年10月7日
* Author: Administrator
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10011;
bool u[maxn];
int su[maxn];
int num = 0;
void prepare() {
int i, j;
memset(u, true, sizeof(u));
for (i = 2; i < maxn; ++i) {
if (u[i]) {
su[++num] = i;
}
for (j = 1; j <= num; ++j) {
if (i * su[j] > maxn) {
break;
}
u[i * su[j]] = false;
if (i % su[j] == 0) {
break;
}
}
}
}
bool pri(int x) {
if (x <= 10010) {
return u[x];
}
int i;
for (i = 1; i <= num; ++i) {
if (x % su[i] == 0) {
return false;
break;
}
}
return true;
}
int main() {
prepare();
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int i, j;
int s[n + 1];
s[0] = 0;
for (i = 1; i <= n; ++i) {
scanf("%d", &s[i]);
s[i] += s[i - 1];
}
bool ok = false;
for (i = 2; i <= n; ++i) {
for (j = 1; j + i - 1 <= n; ++j) {
int k = s[i + j - 1] - s[j - 1];
if (pri(k)) {
ok = true;
printf("Shortest primed subsequence is length %d:", i);
for (k = 1; k <= i; ++k) {
printf(" %d", s[j + k - 1] - s[j + k - 2]);
}
printf("\n");
break;
}
}
if (ok) {
break;
}
}
if (!ok) {
printf("This sequence is anti-primed.\n");
}
}
return 0;
}
分享到:
相关推荐
易语言源码易语言取大素数源码.rar
能够在线性时间内筛出素数,并且对于计算欧拉函数值
ex_08_05筛法素数作业.cpp
69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数...
素数检测.rar素数检测.rar素数检测.rar素数检测.rar素数检测.rar素数检测.rar 素数检测.rar素数检测.rar素数检测.rar素数检测.rar素数检测.rar素数检测.rar
欧拉筛判断素数方法的C语言实现。 欧拉筛法,简称欧拉筛或是欧式筛,又因为其O(n)的时间复杂度而被称为线性筛。 欧拉筛将合数分解为(最小质因数 * 一个合数)的形式,通过最小质因数来判断当前合数是否已经被标记...
4--[scratch算法练习-找素数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码4--[scratch算法练习-找素数].zip源码scratch2.0 3.0编程项目源文件源码案例素材源代码4--[scratch算法练习-找素数].zip源码...
自定义函数求素数(质数).py
算法-求一亿以内的回文质数(素数).rar
判断质数的改进方法。
素数筛.cpp
求2到任意的整数之间的素数.....只输入一个任意的整数就有结果.... 是用C#写的窗体应用程序...适合与做作业....很不错的哦..........
判断一个数是否为素数 素数3.c 使用C语言来实现的
素数1.cpp
素数输出.exe
易语言取素数源码.zip
1000以内素数3.ilk
1026 素数回文.cpp
判断一个数是否为素数 判断素数4.cpp 使用C++来判断
反素数序列.cpp