首页 > 代码库 > SGU 231 Prime Sum 求<=n内有多少对素数(a,b)使得a+b也为素数 规律题
SGU 231 Prime Sum 求<=n内有多少对素数(a,b)使得a+b也为素数 规律题
题目链接:点击打开链接
题意:
求<=n内有多少对素数(a,b)使得a+b也为素数
思路:
我们发现所有素数间隔都是>=2的,且除了2都是奇数,那么:
奇数+奇数 = 偶数。
所以只有一种情况2+素数=素数。
所以打个素数表,看一下有多少个素数和前面那个素数间隔是2的。
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <set> #include <algorithm> using namespace std; #define N 88498 typedef int ll; ll prime[N], primenum, ans[N]; void PRIME(ll Max_Prime){ primenum = 0; prime[primenum++] = 2; for(ll i = 3; i <= Max_Prime; i+=2) for(ll j = 0; j < primenum; j++) if(i%prime[j]==0)break; else if(j == primenum-1 || prime[j] > sqrt((double)i)) { prime[primenum++] = i; break; } } int n; void solve(){ int pos = lower_bound(prime, prime+primenum, n)-prime; if(prime[pos]!=n)pos--; printf("%d\n", ans[pos]); for(int i = 1; i <= pos; i++) if(ans[i-1]!=ans[i]) printf("2 %d\n", prime[i-1]); } int main(){ PRIME(1000000); // for(int i = 0; i <= 10; i++)printf("%d ", prime[i]); // printf("%d\n", primenum); memset(ans, 0, sizeof ans); for(int i = 1; i < primenum; i++) { if(prime[i-1] == prime[i] - 2) ans[i]++; } for(int i = 1; i < primenum; i++) ans[i] += ans[i-1]; while(~scanf("%d",&n)) solve(); return 0; }
SGU 231 Prime Sum 求<=n内有多少对素数(a,b)使得a+b也为素数 规律题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。