题目大意: 给定两个数,要求产生这两个数之间的所有质数。
两个数位m和n,其范围如下:
The input begins with the number t of test cases in a single line (t<=10). In each of the
next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
看似简单的题目,其实也不简单,一般的质数判断方法是,看这个数n能否被2到根号n之间的数除尽,如果不能,那么就是质数,当然,这里这么写程序是会超时的。
查表方法也不行,如果先产生所有的质数表,那么内存太大了,不能保存。一般现在都使用区间剔除的方法。
目前我知道的本题最快的就是二次区间剔除的方法了:
1 先产生2到32000(32000的平方大于1E9)之间的质数,作为一个质数表(增加这个质数表也是为了加速)
2 再产生n到m之间的所有质数
如何产生质数表? 这都是用到往前搜索,剔除不符合条件的数,避免过多的重复计算,带点动态规划的味道。
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
class PrimeNumberGenerator
{
const static int MAX_NUM = 32000;
int PRIMES[MAX_NUM];
int segPrimes[100000];
public:
PrimeNumberGenerator()
{
memset(PRIMES, 0, sizeof(PRIMES));
int j = 0;
for (int i = 2; i < MAX_NUM; i++)
{
if (!PRIMES[i])
{
PRIMES[j++] = i;
for (int k = i*2; k < MAX_NUM; k+=i)//不是k++注意
{//写成 k = i+1,头痛错误!!!
PRIMES[k] = 1;
}
}
}
PRIMES[j++] = MAX_NUM;
}
//本题不需使用的函数
bool isPrimeNum(int num)
{
if (2 == num) return true;
int i = 0;
for ( ; PRIMES[i] * PRIMES[i] <= num && num % PRIMES[i]; i++);
return MAX_NUM != PRIMES[i] && num % PRIMES[i] != 0;
}
void getSegPrimes(int a, int b)
{
memset(segPrimes, 0, sizeof(segPrimes));//每一次都需要memset
for (int i = 0; PRIMES[i]*PRIMES[i] <= b; i++)//错误写成i <= b-a
{
int am = a/PRIMES[i];
for (int d = am; d * PRIMES[i] <= b; d++)
{
if (d > 1 && d * PRIMES[i] >= a) segPrimes[d*PRIMES[i]-a] = 1;
}//这里不能少了判断条件d>1
}
}
void judgePrimes()
{
int a = 0, b = 0;
int T = 0;
cin>>T;
while (T--)
{
cin>>a>>b;
if (a < 2) a = 2;
getSegPrimes(a, b);
for (int i = a ; i <= b; i++)
{
if (0 == segPrimes[i-a]) cout<<i<<endl;
}
cout<<endl;
}
}
};
int main()
{
PrimeNumberGenerator pri;
pri.judgePrimes();
return 0;
}
分享到:
相关推荐
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
8 point fft matlab and simulink.
RandomGoCode:算法,SPOJ,涂鸦...但是在Go中!
SPOJ 应对spoj.com的挑战
Online Judge Problem solution VN.SPOJ
2.1.2 素数筛选(筛选出小于等于 MAXN 的素数) . . . . . . . . . . . . . . . 25 2.1.3 大区间素数筛选(POJ 2689) . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 素数筛选和合数分解 . . . . . . . . ....
My solution for some spoj problems
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
SPOJ 解决来自难题
spoj reverse 的solution
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...
杨弋SPOJ做题表格
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
SPOJ( )上选定问题的解决方案
poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 isap 最快(ek会超时) poj2832 并查集边的计算 sgu218 hcraft 二分图匹配验证 二分答案
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
这是针对SPOJ问题HMRO的测试用例的生成器-帮助军事招募办公室! 如果您有任何建议,请随时通过给我发送电子邮件,并在编辑代码后随时发送请求:) 如何使用: Linux: 通过以下命令编译文件GENERATOR.cpp: g++ -o ...
检测资本(bruitForce(2m,40%daster),计算大写(1ms,99.55%快)) 705 - Hashmap 实现 121 - 买卖股票的最佳时机 力扣 SQL 595 - 大国 - 使用联合运算符的地方......第二个方法 - 或运算符 627 - 交换工资 - ...
SPOJ-Solutions:SPOJ算法问题的解决方案