Friday, October 18, 2019


Spoj -TDPRIMES - Printing some primes


Idea: Use Bitwise Seive.

Code First Then See Solution

Code:
#include <bits/stdc++.h>

using namespace std;
#define mx 100000000

int a[(mx>>5)+2];

bool status(int n,int pos)
{
    return bool(n&1<<pos);
}

int sett(int n,int pos)
{
    return n=n|(1<<pos);
}

int main()
{
    int n= 100000000;
    vector <int> v;
    for(int i=3;i<=sqrt(n);i+=2)
    {
        if(status(a[i>>5],i&31)==false)
        {
            for(int j=i*i;j<=n;j+=i)
            {
                a[j>>5]=sett(a[j>>5],j&31);
            }
        }
    }
    v.push_back(2);
    for(int i=3;i<=n;i+=2)
    {
        if(status(a[i>>5],i&31)==false)
            v.push_back(i);
    }
    for(int i=0;i<=v.size();i+=100)
        cout<<v[i]<<endl;
    return 0;
}

No comments:

Post a Comment