HackerEarth Special graphs problem solution

In this HackerEarth Special graphs problem solution There exist a graph with N nodes that are numbered from 1 to N. There exists an edge between two nodes (u, v). Now, u! = v if u divides v or vice versa. Node 1 is not connected to any other node.

Find the minimum size of set S of nodes such that all the nodes of this graph except node 1 is covered by this set. A node is said to be covered if it is present in this set or there exists at least one node in the set with which it is directly connected, that is, there is an edge between them.

You must cover all the nodes but not the edges.

HackerEarth Special graphs problem solution.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int prime[1000009];

void sieve(int n)
{
    bool pr[n+1];
    for(int i = 1 ; i <= n ; i++)
        pr[i] = true;

    pr[1] = false;

    for(int i = 2 ; i <= sqrt(n) ; i++)
    {
        if(pr[i])
        {
            for(int j = i*i ; j <= n ; j += i)
            {
                pr[j] = false;
            }
        }
    }

    for(int i = 2 ; i <= n ; i++)
    {
        if(pr[i] == true)
        {
            prime[i]++;
        }
    }

    for(int i = 2 ; i <= n ; i++)
    {
        prime[i] += prime[i-1];
    }
}

int main(){
    sieve(1000000);

    int q;
    cin>>q;

    while(q--)
    {
        int n;
        cin>>n;

        cout<<prime[n]<<endl;
    }
}

HackerEarth Special graphs problem solution.

Leave a Reply