优化素数序列

Question

我卡在了 Codechef 实践问题中等难度的问题上：

Shridhar wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers

Rest of the description, I/O format, Test cases examples on this question link

我的实现的问题是得到一个 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("%lld\n", i);
        else if ( ifPrime(i) ) printf("%lld\n", 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("%lld\n", i);  
        } printf("\n");
    }
}

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

Answer 2

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

优化素数序列

Optimizating Prime Number Sequence

c++

algorithm

analysis