LightOj 1259 - Goldbach`s Conjecture

By - 

 // Accepted
// Time:: 0.280
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define sq(x) ((x)*(x))
#define MX 10000009
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define inf 2147483647
#define bn begin()
#define ed end()

using namespace std;

bool flag[MX];
vector <ull>v;
ull plen;

void seieve()
{
    mem(flag,false);

    flag[0]=flag[1]=true;

    ull i,j,qrt=(unsigned long)sqrt(double(MX));

    for(i=4;i<=MX;i+=2)flag[i]=true;

    for(i=3;i<=qrt;i+=2)
    {
        if(!flag[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                flag[j]=true;
            }
        }
    }

    for(i=2;i<=MX;i++)
    {
        if(!flag[i])
        {
            v.push_back(i);
        }
    }

    plen=v.size();
}

int main()
{
    seieve();
    ull i;
    //lp1(i,plen) cout << v[i] << " ";
    int t,tc=1;
    sf("%d",&t);

    while(t-- and tc++)
    {
        ull i,n,half,cnt=0;

        sf("%llu",&n);

        half=n/2;

        for(i=0;v[i]<=half;i++)
        {
            if(!flag[n-v[i]])
            {
                cnt+=1;
            }
        }

        pf("Case %d: %llu\n",tc-1,cnt);
    }

    return 0;
}

 // Accepted
// Time:: 0.516
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define sq(x) ((x)*(x))
#define MX 10000009
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define inf 2147483647
#define bn begin()
#define ed end()

using namespace std;

bool flag[MX];
vector <ull>v;
ull plen;

void seieve()
{
    mem(flag,false);

    flag[0]=flag[1]=true;

    ull i,j,qrt=(unsigned long)sqrt(double(MX));

    for(i=4;i<=MX;i+=2)flag[i]=true;

    for(i=3;i<=qrt;i+=2)
    {
        if(!flag[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                flag[j]=true;
            }
        }
    }

    for(i=2;i<=MX;i++)
    {
        if(!flag[i])
        {
            v.push_back(i);
        }
    }

    plen=v.size();
}

int main()
{
    seieve();
    ull i;
    //lp1(i,plen) cout << v[i] << " ";
    int t,tc=1;
    sf("%d",&t);

    while(t-- and tc++)
    {
        ull i,n,half,cnt=0;

        sf("%llu",&n);

        half=n/2;

        for(i=0;i<plen;i++)
        {
            if(v[i] <= half)
            {
                ull b=n-v[i];

                if(!flag[b])
                {
                    if(b>=v[i])
                    {
                        cnt+=1;
                    }
                }
            }

            else break;
        }

        pf("Case %d: %llu\n",tc-1,cnt);
    }

    return 0;
}

Comments

Post a Comment

Popular posts from this blog

SPOJ-CMG - Collecting Mango

By -
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<stack> #include<map> #include<cmath> #include<algorithm> #define psb push_back #define ppb pop_back #define all(x) x.begin(),x.end() #define N 1000100 #define sf scanf #define pf printf using namespace std; typedef long long LL; typedef vector<LL>vll; LL ar[N] , num[N]; int main() {     int t , tc=0;     //cin >> t;     sf("%d",&t);     while(t--)     {         LL n, x, arlen=-1, nmlen=-1 , i , maxi=-1 , zar;         char c;         //cin >> n;         sf("%lld",&n);         //cout << "Case " << ++tc << ":\n";       ...
Read more

Hackerearth Bishu and his Girlfriend

By -
/* Lionel Messi is such a player that you may catch him, you may touch him, you may feel him and definitely you may Love him. Lionel Messi is Messi. A little Magician in this World. */ // Accepted #include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0) #define bfast cin.tie(0) #define outs(x) cout << x << " " #define outn(x) cout << x << "\n" #define sf scanf #define pf printf #define nl puts("") #define psb push_back #define loop0(n) for(int i=0; i<n; i++) #define loop1(n) for(int i=1; i<=n; i++) #define mpair(x , y) make_pair(x , y) #define all(x) x.begin(), x.end() #define pi acos(-1.0) #define psb push_back typedef unsigned long long ull; typedef long long LL; typedef vector<int>vii; typedef vector<LL>vll; typedef vector<string>vs; typedef map<int, int>mpii; typedef map<string, int>mpsi; typedef map<char, int>mpci; typedef map<LL, LL>mpll; cons...
Read more

Uva 10650 - Determinate Prime

By -
/*     Verdict : Accepted     Link: Determinate Prime Solution Link */ #include<bits/stdc++.h> #define limit 32009 #define sf scanf #define pf printf using namespace std; typedef long long LL; typedef vector<int>vi; int prm[limit], plen=1; bitset<limit> bs; void sieve() {     LL i,j;     bs.set();     bs[1] = bs[0] = 0;     for(i=2; i<limit; i++)     {         if(bs[i])         {             if(i != 2)             {                 prm[plen++] = i;             }          ...
Read more