题目链接:https://vjudge.net/problem/POJ-2739
输入一个数字n,判断有没有一段连续的素数之和大于n,如果有,计算总共有几种。
思路:用素数筛法求出10000以内的素数,然后可以用尺取法计算,我这里是计算先打表计算所有编号为i到编号为j的素数之和,然后再循环查找。
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int vis[],num[],sum[][];
int n,m,k,t,cnt;
void play_table()
{
memset(vis,,sizeof(vis));
memset(sum,,sizeof(sum));
cnt=;
for(int i=;i<=;i++)
{
if(!vis[i])
{
num[++cnt]=i;//记录素数
vis[i]=;
for(int j=i*;j<=;j+=i)
vis[j]=;
}
}
for(int i=;i<=cnt;i++)//计算i到j的和
{
for(int j=i;j<=cnt;j++)
{
sum[i][j]+=sum[i][j-]+num[j];
}
}
}
int main()
{
play_table();
while((cin>>n)&&n)
{
int ans=;
for(int i=;i<=cnt;i++)
{
if(num[i]>n)
break;
for(int j=i;j<=cnt;j++)
{
if(sum[i][j]>n)
break;
if(sum[i][j]==n)
{
ans++;
}
}
}
cout<<ans<<endl;
}
return ;
}
筛素数 poj 2739的更多相关文章
-
POJ 2739 Sum of Consecutive Prime Numbers(素数)
POJ 2739 Sum of Consecutive Prime Numbers(素数) http://poj.org/problem? id=2739 题意: 给你一个10000以内的自然数X.然 ...
-
poj 2689 Prime Distance(大区间筛素数)
http://poj.org/problem?id=2689 题意:给出一个大区间[L,U],分别求出该区间内连续的相差最小和相差最大的素数对. 由于L<U<=2147483647,直接筛 ...
-
Prime Path(POJ - 3126)【BFS+筛素数】
Prime Path(POJ - 3126) 题目链接 算法 BFS+筛素数打表 1.题目主要就是给定你两个四位数的质数a,b,让你计算从a变到b共最小需要多少步.要求每次只能变1位,并且变1位后仍然 ...
-
Sum of Consecutive Prime Numbers POJ - 2739 线性欧拉筛(线性欧拉筛证明)
题意:给一个数 可以写出多少种 连续素数的合 思路:直接线性筛 筛素数 暴力找就行 (素数到n/2就可以停下了,优化一个常数) 其中:线性筛的证明参考:https://blog.csdn.net ...
-
POJ 2689.Prime Distance-区间筛素数
最近改自己的错误代码改到要上天,心累. 这是迄今为止写的最心累的博客. Prime Distance Time Limit: 1000MS Memory Limit: 65536K Total S ...
-
POJ中和质数相关的三个例题(POJ 2262、POJ 2739、POJ 3006)
质数(prime number)又称素数,有无限个.一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该数除了1和它本身以外不再有其他的因数:否则称为合数. 最小的质数 ...
-
ACM:POJ 2739 Sum of Consecutive Prime Numbers-素数打表-尺取法
POJ 2739 Sum of Consecutive Prime Numbers Time Limit:1000MS Memory Limit:65536KB 64bit IO Fo ...
-
POJ-2689 Prime Distance (两重筛素数,区间平移)
Prime Distance Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13961 Accepted: 3725 D ...
-
欧拉函数O(sqrt(n))与欧拉线性筛素数O(n)总结
欧拉函数: 对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目. POJ 2407.Relatives-欧拉函数 代码O(sqrt(n)): ll euler(ll n){ ll ans=n; ...
随机推荐
-
推荐!国外程序员整理的 C++ 资源大全
http://blog.jobbole.com/78901/ 关于 C++ 框架.库和资源的一些汇总列表,由 fffaraz 发起和维护. 内容包括:标准库.Web应用框架.人工智能.数据库.图片处理 ...
-
html 标签总结
<q>标签,短文本引用 例如“聪明秀出为之英,胆略过人为之雄.” <blockquote>标签,长文本引用 <blockquote>标签的解析是缩进样式. 没有HT ...
-
JavaScript的问题
定义一个函数function, function testParams() { var params = ""; for(var i=0; i<arguments.lengt ...
-
Centos7 打开80端口防火墙命令
iptables -I INPUT -p TCP --dport 80 -j ACCEPT
-
[python笔记][第二章Python序列-list]
2016/1/27学习内容 第二章 Python序列-list list常用操作 list.append(x) list.extend(L) list.insert(index,x) list.rem ...
-
9 个用于移动APP开发的* JavaScript 框架
* Java 框架 对于Web开发而言,Java是一个有前途的编程语言,并且在不久的将来它将依然在这个领域大放光彩.Java在移动app开发上也有同样的影响吗?让我们一起来看看ValueCoders ...
-
网站性能优化实战——从12.67s到1.06s的故事
文章摘自https://juejin.im/post/5b0b7d74518825158e173a0c 作为互联网项目,最重要的便是用户体验.在举国“互联网+”的热潮中,用户至上也已经被大多数企业所接 ...
-
hashcat使用命令简介
1.指定HASH类型 在HashCat中--hash-type ?参数可以指定要破解的HASH类型,运行hashcat主程序加上--help参数,在* Generic hash types:中可以看到 ...
-
结合 Redis 实现同步锁
1.技术方案 1.1.redis的基本命令 1)SETNX命令(SET if Not eXists) 语法:SETNX key value 功能:当且仅当 key 不存在,将 key 的值设为 val ...
-
Beta 冲刺 五
团队成员 051601135 岳冠宇 031602629 刘意晗 031602248 郑智文 031602330 苏芳锃 031602234 王淇 照片 项目进展 岳冠宇 昨天的困难 数据交换比较复杂 ...