Can I optimize more in Sieve of Eratosthenes implementation ?

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

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 Sukarna_Paul 2019-02-22 10:09:19 1761 Initial revision (published)