শুক্রবার, ৩০ ডিসেম্বর, ২০১৬

UVA 10311 - Goldbach and Euler

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

#define SIZE 100000001

char  status[SIZE]={0};
void sieve()
{
 long int i,j;
 int sq = sqrt(SIZE);
 for(i=3;i<=sq;i+=2)
   {
       {
            for(j=i*i;j<=SIZE;j+=2*i)
                status[j]=1;
       }
   }
   status[1]=1;
   status[0]=1;
   for(i=1;i<=SIZE;i++)
   {
       if(i%2==0&&i!=2)
       {
           status[i]=1;
           continue;
       }
   }

}

int main()
{
 unsigned long long int n;
 sieve();
 while(scanf("%llu",&n)==1)
 {
     unsigned long long i1,k1,flag=0,m;
     if(n%2==1)
     {
         if(n==1)
            printf("%llu is not the sum of two primes!\n",n);
         else if(status[n-2]==1)
         {
             printf("%llu is not the sum of two primes!\n",n);
         }
         else
             printf("%llu is the sum of 2 and %llu.\n",n,n-2);
     }
     else
     {
         m=0,flag=0;
         for(i1=n/2;i1<n;i1++)
         {
             if(status[(n/2)-m]==0 && status[i1]==0 && ((n/2)-m)!=i1)
             {
                 flag=1;
                 printf("%llu is the sum of %llu and %llu.\n",n,n-i1,i1);
                 break;
             }
             m++;
         }
     if(flag==0)
            printf("%llu is not the sum of two primes!\n",n);
     }
 }

}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...