Can I optimize more in Sieve of Eratosthenes implementation ?

Revision en1, by Sukarna_Paul, 2019-02-22 10:09:19

I was solving the problem from SPOJ Link . But my solution is getting TLE. Please help me out!

Here is my solution :

#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define pli pair<long long , int>
#define pil pair<int ,long long>
#define pi acos(-1)
#define pb push_back
#define mkp make_pair
#define all(a) a.begin(), a.end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}
using namespace std;

vector <ll> prime;
bitset <100000010> bs;

void sieve ()
{
	bs.set ();
    prime.pb(2LL);
	for (ll i = 3; i < 100000000; i+=2)
	{
		if (bs[i])
		{
			prime.pb(i);
			for (ll j = i * i; j < 10000000; j += i+i)
			{
				bs[j] = 0;
			}
		}
	}
}

int main(){
    IOS
    //freopen("output.txt","w",stdout);
    sieve();
    int i=0;
    unordered_map<int,int>r,c;

    for(auto it=prime.begin();it!=prime.end();){
        i++;
        for(int j=1;j<=i;j++){
            r[(*it)]=i;
            c[(*it)]=j;
            it++;
        }
    }
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int a;
        cin>>a;
        if(r[a]==0){
            cout<<"-1"<<endl;
            continue;
        }
        cout<<r[a]<<" "<<c[a]<<endl;

    }
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Sukarna_Paul 2019-02-22 10:09:19 1761 Initial revision (published)