UVA solution

Prime Numbers

UVA 406 : Prime Cuts

#include<iostream>
#include<cstdio>
#include<vector>
#include<math.h>
using namespace std;

int main()
{
    int n;int k=0,c;
    vector<int>arra(100000,0),prime;
    arra[0]=1;
    arra[1]=0;
    for(long long int i=2;i*i<=100000;i++)
    {
        if(arra[i]==0)
            {
                for(long long int j=i+i;j<=100000;j+=i)
                {
                    arra[j]=1;
                }
            }
    }

    for(long long int i=0;i<=100000;i++)
    {
        if(arra[i]==0)
            prime.push_back(i);
    }//printf("%d  ",prime[prime.size()-1]);cout<<prime.size();


    while(scanf("%d%d",&n,&c)==2)
    {
        int r=c,value,i,carry,mid,low,high,cntr=0;
        for(i=0;i<prime.size();i++)
        {
            if(n<prime[i])
            {
                i--;break;
            }
        }
        double val=(double)i;
        val/=2;//cout<<val<<endl;
        mid=ceil(val);//cout<<mid<<endl;
        if(i%2==1)//
        {low=mid-c;   high=mid+c-1;/*cout<<"fg"<<prime[high]<<endl;*/ if(prime[high]>n) cntr++;  }//if n=c=1000 then prime[high]=8693 if n=c=2000 prime[high]=18911,prime[high] is so large bcoz high=mid+c-1,here c is a big value
        else
        {
            c=c*2-2;c/=2; low=mid-c; high=mid+c;/*cout<<"hh"<<prime[high]<<endl;*/  if(prime[high]>n) cntr++;
        }
        printf("%d %d:",n,r);
        if(cntr!=0)
           for(i=0;prime[i]<=n;i++)
                printf(" %d",prime[i]);
        else
            for(i=low;i<=high;i++)
                printf(" %d",prime[i]);
        cout<<endl<<endl;
        }
    return 0;
}


UVA 10394 : Twin Prime

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

int main()
{
    int cntr[200000][2],pair_no;int k=0;
    vector<int>arra(21000000,0);
    arra[0]=1;
    arra[1]=1;
    for(long long int i=2;i*i<=21000000;i++)
    {
        if(arra[i]==0)
            {
                for(long long int j=i+i;j<=21000000;j+=i)
                {
                    arra[j]=1;
                }
            }
    }

    for(long long int i=2;i<=21000000;i++)
        {
            if(arra[i]==arra[i-2] && arra[i]==0 )
                    {
                        k++;
                        cntr[k][0]=i-2;cntr[k][1]=i;
                    }
        }

    while(scanf("%d",&pair_no)==1)
    {
        printf("(%d, %d)\n",cntr[pair_no][0],cntr[pair_no][1]);
    }
    return 0;
}


UVA 543 : Goldbach Conjecture


#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

int main()
{
    int cntr[200000][2],n;int k=0;
    vector<int>arra(1000000,0),prime;
    arra[0]=1;
    arra[1]=1;
    for(long long int i=2;i*i<=1000000;i++)
    {
        if(arra[i]==0)
            {
                for(long long int j=i+i;j<=1000000;j+=i)
                {
                    arra[j]=1;
                }
            }
    }

    for(long long int i=2;i<=1000000;i++)
        {
            if(arra[i]==arra[i-2] && arra[i]==0 )
                    {
                        k++;
                        cntr[k][0]=i-2;cntr[k][1]=i;
                    }
        }
      for(long long int i=3;i<=1000000;i++)
    {
        if(arra[i]==0)
            prime.push_back(i);
    }//printf("%d  ",prime[prime.size()-1]);cout<<prime.size();

    while(scanf("%d",&n)==1 && n!=0)
    {
        int value,i,carry;
        for(i=0;i<prime.size();i++)
        {
            value=n-prime[i]; int low=i,high=prime.size()-1,mid;
            while(low<=high)
            {
              mid=(low+high)/2;
                //printf("i=%d %d %d %d low=%d high=%d %d\n",i,prime[i],mid,prime[mid],low,high,value);
                // printf("i=%d %d %d\n",i,prime[i],mid,prime[mid]);
                if(prime[mid]>=value)
                    if(prime[mid]==value)
                        {carry=value;break;}
                    else
                        high=mid-1;
                else
                    low=mid+1;
            }
            if(carry==value)
                break;
        }
        printf("%d = %d + %d\n",n,prime[i],carry);
    }
    return 0;
}