CODEWITHSUNDEEP
c++algorithmanalysis
Martin Gardener
Martin Gardener

Reputation: 1001

Optimizating Prime Number Sequence

I am stuck on a questions from Codechef practice problems difficulty medium with problem statement:

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

The problem with my implementation is getting a TLE (Time Limit Exceeded) and wish to solve this problem, can you point out any problem in my implementation, I can't seem to figure it out after hours of dry run.

Includes, Directives and ifPrime function

#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;
}

Generate Prime Function

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");
}

Main

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);

    }
}

I can't think of another solution to this problem, the only way I came up is memoization, and it is also handling large integers as well. Help needed.

Upvotes: 2

Views: 149

Answers (2)

Sebastian Martin Dicke
Sebastian Martin Dicke

Reputation: 16

You should consider to use std::unordered_map instead of std::map. Often std::map is implemented with trees and std::unordered_map with hash tables. Operations on hash tables are normally faster on modern computers than operations on trees.

Upvotes: 0

Danyal Imran
Danyal Imran

Reputation: 2605

The approach has a problem that it is generating memoization key, value pairs. Probably they should be tested immediately instead of saving them.

An easy solution is to iterate over the range m<=x<=n and then check if the number is prime using the optimized prime checker algorithm which takes around (O((n-m)^1/2)), which is quiet less for very large numbers.

Prime function

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;
}

and you main as

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");
    }
}

I've tried to code according to your macro definitions, hope it helps :)

Upvotes: 3

Related Questions