SGU 231 解题手记
A一定等于2,否则A+B就是偶数了。这就简单了,把N以下的质数求出来就完了。
注意10^6=1000000,可不是100000。1000000以下的质数有80000多个。
不行,这个算法太慢了。看了天皇的程序,MS也是类似的想法。但天皇是筛法求质数,筛法比朴素的判定法更快吗?又看Amber的程序,居然也是筛法求质数,而且注了个复杂度O(n)。
Submit 1: WA on 3。不知道是不是该算PE,个数和序列输出反了。
Submit 2: AC。这都能AC……假的吧……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | //AC #include <iostream> using namespace std; void get_primes(long n,long *primes) { *primes=0; for (long i=2;i<=n;++i) { bool isprime=true; for (long j=1;j<=*primes && *(primes+j) * *(primes+j)<=i;++j) if (i % *(primes+j) ==0) { isprime=false; break; } if (isprime) *(primes+ ++*primes)=i; } } int main() { long n,c(0); long primes[100000]={0},bprimes[10000]={0}; cin>>n; get_primes(n,primes); for (long i(2);i<primes[0];) if (primes[i]+2==primes[++i]) { bprimes[++bprimes[0]]=primes[i]-2; ++c; } cout<<c<<endl; for (long i(1);i<=bprimes[0];cout<<2<<' '<<bprimes[i++]<<endl); return 0; } |

3 Responses
- -假的。。我先用cout然后改printf都TLE
跟你算法差不多
Reply
1128741 05.01.11 20:20 bslgh_majia 231 .CPP Accepted 582 ms 407 kb
Reply
- -是我代码丑了
Reply