优化质数序列

Question

我被困在Codechef练习问题难度中等的问题上，问题陈述：

Shridhar希望为他的密码系统生成一些素数。 帮帮他！你的任务是生成两个给定之间的所有素数 数字

其余描述、I/O 格式、此问题链接上的测试用例示例

我的实现的问题是获得TLE(超过时间限制(并希望解决这个问题，您能否指出我的实现中的任何问题，经过数小时的试运行，我似乎无法弄清楚。

包含、指令和 ifPrime 函数

#include<map>
#include<math.h>
#include<stdio.h>
#define LLD long long int
#define REPNE(i,a,b) for(LLD i=a; i<=b; ++i)
#define REPNEI(i,a,b,k) for(LLD i=a; i<=b; i+=k)
using namespace std;
map<LLD, bool> mem;
bool ifPrime ( LLD a ) {
if ( a<2 ) return false;
else if ( a==2 ) return true;
else if ( a%2==0 ) return false;
REPNEI(i,3,sqrt(a),2) {
if ( a%i==0 ) return false;
}
mem[a] = true;
return true;
}

生成素数函数

void genPrime ( LLD a, LLD b ) {
REPNE(i,a,b) {
if ( mem.find(i) != mem.end() ) printf("%lldn", i);
else if ( ifPrime(i) ) printf("%lldn", i);
} printf("n");
}

主要

int main ( ) {
// freopen("input.txt", "r", stdin);
int t; scanf("%d", &t);
REPNE(test, 1, t) {
LLD a, b;
scanf("%lld %lld", &a, &b);
genPrime(a,b);
}
} 

我想不出这个问题的另一种解决方案，我想出的唯一方法是记忆，它也在处理大整数。需要帮助。

Answer 1

该方法存在一个问题，即生成记忆键、值对。可能应该立即测试它们而不是保存它们。

一个简单的解决方案是遍历范围m<=x<=n然后使用优化的素数检查器算法检查数字是否是素数，该算法需要大约 (O((n-m(^1/2((，这对于非常大的数字来说不太安静。

素数函数

bool ifPrime ( int n ) {
if ( n==2 ) return true;
else if ( n%2==0 || n<=1 ) return false;
for ( int i=3; i<=sqrt(n); i+=2 ) {
if ( n%i==0 ) return false;
}
return true;
}

而你主要作为

int main ( ) {
int t; scanf("%d", &t);
REPNE(test, 1, t) {
LLD a, b;
scanf("%lld %lld", &a, &b);
REPNE(i,a,b) {
if ( ifPrime(i) ) printf("%lldn", i);  
} printf("n");
}
} 

我尝试根据您的宏定义进行编码，希望对您有所帮助:)

Answer 2

你应该考虑使用 std：：unordered_map 而不是 std：：map。通常 std：：map 是用树实现的，std：：unordered_map 是用哈希表实现的。在现代计算机上，对哈希表的操作通常比对树的操作更快。