求一个数分解成两个素数的方案数(线性筛素数)

https://vjudge.net/contest/219676#problem/D

题意:让你找出两个素数相加等于n的对数 T (≤ 300),4 ≤ n ≤ 107

(本题典型的线性筛素数,只要注意定义时使用bool而不使用int,并且在合成n时 使用if(isprime[n-prime[i]])将复杂度由O(n^2)降为O(n)即可)

由T和n的数据量可知需要实现把素数筛出来,、

而素数线性筛法由于需要的数组的大小与n一致,为1e7,所以尤其耗内存,容易MLE,所以在设置isprime[]数组时定义为bool,另外在检查是否能合成n时,将复杂度降为O(n)

bool isprime[10000005]  与 int isprime[10000005]一个AC,一个MLE(一般题目能容忍的是1e7个int,int占4个字节,而bool占1个字节)

1、线性筛,用bool定义notprime[10000005],否则TLE

2、使用if(notprime[a-prime[i]])将复杂度降为O(n)

原文地址:https://www.cnblogs.com/MekakuCityActor/p/8710983.html