Composites and Primes Sieve of Eratosthenes dp

-
/*

Given two integers L and R find the difference of number of composites and primes between the range L and R (both inclusive).
Input:
First line of input contains of an integer 'T' denoting number of test cases . Then T test cases follow.
Each test contains two integers L and R .

Output:
For each case print an integer corresponding to the answer .

Constraints:
1<=T<=100
1<=L<=R<=10^7

Example:

Input:
2
4 4
4 6
Output:
1
1
*/
// given l , r print no of comp- no of prime  T.C->0.21
// normal approac i*i<=n gives TLE > 3.14
#include<bits/stdc++.h>
using namespace std;
bool prime[100001];
void SieveOfEratosthenes()
{
    memset(prime, true, sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for (int p=2; p*p<=10000000; p++)
    {
   
        if (prime[p] == true) // we make all multiples of prime false
        {
            for (int i=p*p; i<=10000000; i += p)  // we make all multiples of prime false
                prime[i] = false;
        }
    }
}
bool checkPrime(int num){
    return prime[num];
}

int main() {
//code
SieveOfEratosthenes();
    int t;
    cin>>t;
    while(t--){
        int l,r;
        cin>>l>>r;
     
        int cn=0,pn=0;
     
        for(int i=l;i<=r;i++){
            if(checkPrime(i) && i>1){
             
               pn++;
            }else{
                if(i>1){
                    cn++;
                }
             
            }
        }
     
        cout<<(cn-pn)<<endl;
     
    }
   return 0;
}

Comments

Post a Comment

Popular posts from this blog

-
// sieve of Atkin is a popular way to find all the prime numbers in range using the dp approach and is //better than the erronthesis approach // C++ program for implementation of Sieve of Atkin #include <bits/stdc++.h> using namespace std;   int SieveOfAtkin(int limit) {     // 2 and 3 are known to be prime     if (limit > 2)         cout << 2 << " ";     if (limit > 3)         cout << 3 << " ";       // Initialise the sieve array with false values     bool sieve[limit];     for (int i = 0; i < limit; i++)         sieve[i] = false;     for (int x = 1; x * x < limit; x++) {         for (int y = 1; y * y < limit; y++) {                           // Main part of Sieve of Atkin             int n = (4 * x * x) + (y * y);             if (n <= limit && (n % 12 == 1 || n % 12 == 5))                 sieve[n] ^= true;               n = (3 * x * x) + (y * y);             if (n <= limit &
Read more

Linked List 10 operations from which problems are made ( complete guide for you)

-
/* These are the functions we will implement make your seatbelts tight and start progrmming cout<<" 1. Insert node at begining"<<endl; cout<<" 2. Append a node"<<endl; cout<<" 3. display the l.l"<<endl; cout<<" 4. Insert before a selected node"<<endl; cout<<" 5. Insert after a selected node "<<endl; cout<<" 6.Delete a particular node"<<endl; cout<<" 7.Reverse A L.L "<<endl; cout<<" 8. Do bot reverse the l.l but display the reversed order (using recursion)"<<endl; cout<<"9. find middle element in a list using slow and fast pointer"<<endl; cout<<"10. check if linked list is palindrome or not (we know if even f=NULL odd f->next=NULL)"<<endl; cout<<" 11. exit"<<endl; */ #include<iostream> using namespace std; struct node{
Read more

Stack - print bracket number

-
/ * example 2 (0+1)*0(0+1)*0(0+1)* (1*0)*1* o/p 1 1 2 2 3 3  1 1  Example: Input: 3 (a+(b*c))+(d/e) ((())(())) ((((() Output: 1 2 2 1 3 3 1 2 3 3 2 4 5 5 4 1 1 2 3 4 5 5 */ #include<bits/stdc++.h> using namespace std; int main()  { int t; cin>>t; while(t--) {     string s;     stack <int> st;     int c=0; // we maintain the count of open brackets     cin>>s;     for(int i=0;i<s.length();i++)     {         if(s[i]=='(')         {c++;         cout<<c<<" ";         st.push(c);         }         if(s[i]==')')         {             cout<<st.top()<<" ";             st.pop();         }     }     cout<<endl; } return 0; }
Read more