Prime Number generator Using Sieve Algorithms

Prime Number Calculate
Using Sieve Algorithms

********Problem 1**********

You are given N, find the Nth prime number...
N:B: 1 is not a prime number
Input Format
Only a number N
Constraints
1 <= N <= 107
Output Format
Y
where Y is the prime number which is at Nth position.
Print "invalid position" when Nth position prime is greater than 107.
Sample Input 0
1
Sample Output 0
2
Explanation 0
first prime number is 2
Sample Input 1
5
Sample Output 1
11
Explanation 1
5th prime number is 11

********Solve********

#include<bits/stdc++.h>
using namespace std;

#define ll long long
vector<int>p;
bitset<10000005>bs;
bool ar[1000005];


bool isprime(long long x)
{
    if(x<=10000005)
    {
        return bs[x];
    }
    for(long long i=0; i<p.size(); i++)
    {
        if(x%p[i]==0)
        {
            return false;
        }
    }
    return true;
}


void seive(long long n)
{
    long long i,j;
    bs.set();
    bs[0]=bs[1]=0;
    for(i=4; i<=10000005; i+=2)
    {
        bs[i]=0;
    }
    for(i=3; i*i<=10000005; i+=2)
    {
        if(bs[i])
        {
            for(j=i*i; j<=10000005; j=j+(2*i))
            {
                bs[j]=0;
            }
        }
    }
    ll c=0,m=n;

    for(ll i=2; i<=10000005; i++)
    {
        if(isprime(i))
        {
            c++;
            m--;
            if(m==0)
            {
                cout<<i<<endl;
                break;
            }
        }
    }
    if(m!=0)
    {
        cout<<"invalid position"<<endl;
    }
}

int main()
{
    long long n;
    cin>>n;
    seive(n);
}


***********************END*************************
******** Problem 2 *******


You are given N, you have to find number of prime numbers existing less than or equal N.
N:B: 1 is not a prime number

Input Format

Only a number N

Constraints

1 <= N <= 106

Output Format

Y
where Y is the correct answer.

Sample Input 0

10
Sample Output 0

4
Explanation 0

2 3 5 7 are prime numbers less then 10

Sample Input 1

5
Sample Output 1

3
Explanation 1

2 3 5 are prime numbers till 5



*******solve Code********


#include<bits/stdc++.h>
using namespace std;
vector<int>p;
bool ar[1000005];
void seive(int n)
{
    for(int i=4; i<=n; i+=2)
    {
        ar[i]=1;
    }
    for(int i=3; i<=n; i+=2)
    {
        if(!ar[i])
        {
            for(int j=i*2; j<=n; j=j+i)
            {
                ar[j]=1;
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        if(!ar[i])
        {
            p.push_back(i);
        }
    }
    cout<<p.size()<<endl;
}


int main()
{
    int n;
    cin>>n;
    seive(n);
}


***********************END********************************

********Problem 3*********

You re given N, find weather N is prime or not.
N:B: 1 is not a prime number

Input Format

only a number N

Constraints

1 <= N <= 107

Output Format

Print " Y is a Prime Number. " is Y is prime number otherwise
Print " Y is not a Prime Number. "

*******solve Code********

#include<bits/stdc++.h>
using namespace std;
vector<int>p;
bitset<10000005>bs;
bool ar[1000005];


bool isprime(long long x)
{
    if(x<=10000005)
    {
        return bs[x];
    }
    for(long long i=0; i<p.size(); i++)
    {
        if(x%p[i]==0)
        {
            return false;
        }
    }
    return true;
}


void seive(long long n)
{
    long long i,j;
    bs.set();
    bs[0]=bs[1]=0;
    for(i=4; i<=n; i+=2)
    {
        bs[i]=0;
    }
    for(i=3; i*i<=n; i+=2)
    {
        if(bs[i])
        {
            for(j=i*i; j<=n; j=j+(2*i))
            {
                bs[j]=0;
            }
        }
    }
    if(isprime(n))
    {
        cout << n << " is a Prime Number.";
    }
    else
    {
        cout << n << " is not a Prime Number.";
    }
}

int main()
{
    long long n;
    cin>>n;
    seive(n);
}