首页 > 学院 > 开发设计 > 正文

HDU-2098

2019-11-14 12:23:19
字体:
来源:转载
供稿:网友

题目:

把一个偶数拆成两个不同素数的和,有几种拆法呢?

代码:

#include<iostream>#include<cmath>#include<cstring>using namespace std;int main(){ long long array[10001]; memset(array,0,sizeof(array)); for(int i = 2,j = 4;i <= 10000;i++,j+=i*2-1) { if(!array[i]) for(int k = j;k < 10000;k += i) array[k] = 1; }//“埃氏筛法” int num = 0; while(cin >> num) { if(num == 0) return 0; int sum = 0; int temp = num/2; for(int i = 2;i <= temp;i++) { int a = num-i; if(!array[i] && !array[a] && a!=i) { sum++; } } cout << sum <<endl; }}

理解:

这道题,题目很明了,但是拿到以后,我不知道怎么拆,一个一个找素数这种暴力方法。。TLE。。。。所以,我想很定是有什么专门的方法来找素数,再查了一下以后,知道了“埃拉托斯特尼筛法”也叫埃氏筛法,是一个很好用的素数筛法。然后利用这个筛法,在进行拆分,就很好解决了。


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表