10168 - Summation of Four Primes

[samin_yasar]

#include <stdio.h>
#include <math.h>
int prime(int n)
{
int i = 3 , j=0;

if(n%2==0 && n!=2)return 0;

if(n==2)return 1;

for(;i <= sqrt(n) ; i+=2)
{
if( (n%i)==0 ) return 0;

else j=1;

}

if(j==1)return 1;

}
void print(int n)
{
int i;
for( i=2 ; i <= n/2 ;i++)
{
if(prime(i))
{
if(prime(n-i))
{
printf("%d %d",i,(n-i));
break;
}
}
}

}

int main()
{
int num,num1,num2;

while(scanf("%d",&num)==1)
{
if(num<8)printf("Impossible.\n");

else if(num==8)printf("2 2 2 2\n");

else if(num>8)
{
if(num%2!=0)
{
num1 = num-5;

printf("2 3 ");

print(num1);

printf("\n");
}
else
{
if( (num/2)%2==0)
{
num1 = num/2-2;

num2 = num/2+2;

print(num1);

printf(" ");

print(num2);

printf("\n");

}
else
{
num1 = num/2-5;

num2 = num/2+5;

print(num2);

printf(" ");

print(num1);

printf("\n");
}

}

}

}
return 0;
}

i'm getting wrong answer with this code. Some one please help me.

[rafay-hasan]

Whats wrong with my code!!!!anyone please help me.


#include<stdio.h>
#include<string.h>
#include<math.h>
#define u 10000000
long prime,a,b,c,d,m=0;
bool tag;
int p()
{
long i,j,x;
memset(tag,true,sizeof(tag));
prime[m++]=2;
for(i=3;i<=u;i=i+2)
{
if(tag)
prime[m++]=i;
if(i<=u/i)
{
x=i<<1;
for(j=i*i;j<=u;j=j+x)
tag[j]=false;
}
}
return 0;
}
int check(int n)
{
long i,remainder,x;
x=sqrt(n);
for(i=0;prime<=n;i++)
{
remainder=n-prime;
if(remainder==2)
{
c=prime;
d=remainder;
break;
}
if(remainder%2!=0 && tag[remainder])
{
c=prime;
d=remainder;
break;
}
}
return 0;
}
int main()
{
long n,x,y;
p();
while(scanf("%ld",&n)==1)
{
a=b=c=d=0;
if(n>=8)
{
if(n%2==0)
{
n=n-4;
a=2;
b=2;
check(n);
printf("%ld %ld %ld %ld\n",a,b,c,d);
}
else
{
n=n-5;
a=2;
b=3;
check(n);
printf("%ld %ld %ld %ld\n",a,b,c,d);
}
}
else
printf("Impossible\n");
}
return 0;
}

[shantanu18]

I am getting WA. There is no lower bound so i handle for negative number also

Code: Select all

#include <cstdio>
#include <iostream>
#include <cmath>
#define MAX 10000100
#define PMAX 664600
#define int64 long long
using namespace std;

bool base[MAX+2];
int64 prime[PMAX+2];
void getPrime()
{
	int i2,cnt=0;
	int sq=sqrt(MAX);
	for(int i=3;i<=sq;i+=2)
	{
		if(!base[i])
		{
			i2=i*2;
			for(int j=i*i;j<=MAX;j+=i2)
				base[j]=true;
		}
	}
	prime[cnt++]=2;
	for(int i=3;i<=MAX;i+=2)
		if(!base[i]) {prime[cnt++]=i;}
}

int main()
{
	getPrime();
	int64 n,half,val;
	while(scanf("%lld",&n)==1)
	{
		bool flag=false;
		if(n<8 && n>=-7) cout<<"Impossible.\n";
		else{
			if(n<0){ flag=true;n=-n;}
			n=n-4;
			if(flag==true)
				cout<<"-2 -2 ";
			else
			cout<<"2 2 ";
			half=n/2;
			for(int i=0;prime[i]<=half;i++)
			{
				
				val = n-prime[i];
				if((val%2!=0 && !base[val]) || val==2)
				{
					if(flag)
						printf("-%lld -%lld\n",prime[i],val);
					else
					cout<<prime[i]<<" "<<val<<endl;
					break;
				}
			}
			
		}
	}
	return 0;
}

[plamplam]

I don't think there are negative numbers in the judge input. My program just outputs Impossible when n < 8. btw this problem can be solved very easily as there are no restrictions. As the problem clearly says that any good solution will do, the problem can be reduced to a much simpler one. Think about it

[Karcher]

int main()
{
int num,num1,num2;

while(scanf("%d",&num)==1)
{
if(num<8)printf("Impossible.\n");

else if(num==8)printf("2 2 2 2\n");

else if(num>8)
{
if(num%2!=0)
{
num1 = num-5;

[Caren]

Can anybody tell why this code gives PE ?? I have looked for every possible case but every time it gives just PE. This same thing is happening with problem 628 also. I have posted about that problem in related thread too. Please help. Thanx in advance

Code: Select all

Removed after AC . Codes were fine.There was an online judge problem . Now it's solved and all the solutions are accepted

[brianfry713]

Post the full code, this won't compile without any includes. There seems to be an issue with all special judges right now always giving PE.

[Caren]

Sorry for the previous post . I posted full code this time.

Code: Select all

AC

[brianfry713]

Resubmit, the judge wasn't working but is now fixed.

[Caren]

Thanks, very much. Resubmitted and got accepted now.

[academus]

Hi all, I think the UVa judge for problem 10168: Summation of Four Primes is incorrect and I have complete confidence: I have test my program with every integer from 8 to 10000000 that can be a sum of 4 primes. The test result shows that my program is OK but the UVa judge gives me WA. I paste my program(in C++) and test program(in Ruby) below, please correct me if I miss something:

Code: Select all

#include <iostream>
#include <vector>

#define MAX_N 10000000

using namespace std;

vector<int> primes;

void init() {
  vector<bool> removed(MAX_N + 1);
  primes.reserve(665000); //There are 664579 prime numbers within 10000000
  primes.push_back(2);
  int i = 3;
  for (; i <= MAX_N; i += 2) {
    if (!removed[i]) {
      primes.push_back(i);
      int s = i + i;
      for (; s <= MAX_N; s += i) {
        removed[s] = true;
      }
    }
  }
}

//The index of a prime p in primes array that is the biggest prime not bigger than n.
int index_of_prime(int n) {
  int r = -1;
  int i = 0;
  int j = primes.size();
  while (i != j) {
    int mid = (i + j) / 2;
    if (primes[mid] == n) {
      r = mid;
      break;
    }
    else if (primes[mid] > n) {
      j = mid;
      if (i == j) {
        r = mid - 1;
      }
    }
    else {
      i = mid + 1;
      if (i == j) {
        r = mid;
      }
    }
  }
  return r;
}

inline bool is_prime(int n) {
  return n < 2 ? false : primes[index_of_prime(n)] == n;
}

bool backtrack(int n, int q, vector<int> & a) {
  int r = false;
  if (q == 1) {
    if (is_prime(n)) {
      a.push_back(n);
      r = true;
    }
  }
  else {
    int i = index_of_prime(n);
    q--;
    for (; i >= 0; i--) {
      if (backtrack(n - primes[i], q, a)) {
        a.push_back(primes[i]);
        r = true;
        break;
      }
    }
  }
  return r;
}

inline bool four_primes(int n, vector<int> & a) {
  if (n < 8)
    return false;
  return backtrack(n, 4, a);
}

int main() {
  init();
  int n;
  while (cin >> n) {
    vector<int> a;
    if (four_primes(n, a)) {
      for (int i = 0; i < 4; i++) {
        if (i)
          cout << ' ';
        cout << a[i];
      }
      cout << endl;
    }
    else {
      cout << "Impossible." << endl;
    }
  }
  return 0;
}

The test file requires a test_helper module which I authored. I haven't past it here because the following code is easy enough to be understood: the test method produces a input file for my C++ program to read as input, and the check_result method opens the output of the C++ program and checks each line to see if it's legal.

Code: Select all

#!/usr/bin/env ruby

require_relative 'test_helper'

PRIMES = []

def produce_primes(n)
  removed = Array.new(n + 1, false)
  PRIMES << 2
  i = 3
  while i <= n
    if !removed[i]
      PRIMES << i
      s = i + i
      while s <= n
        removed[s] = true
        s += i
      end
    end
    i += 2
  end
end

def is_prime(n)
  yes = false
  i = 0
  j = PRIMES.size
  while i != j
    mid = (i + j) / 2
    if PRIMES[mid] == n
      yes = true
      break
    elsif PRIMES[mid] > n
      j = mid
    else
      i = mid + 1
    end
  end
  yes
end

s = 8
e = 10000000
produce_primes(e)

test_file = File.expand_path(__FILE__)
test(test_file) do |input, output|
  input = File.open(input, 'wb')
  (s..e).each do |i|
    input.puts i
  end
  input.close
end

count = 0
i = s
w = []
check_result(test_file) do |result|
  result = File.open(result, 'rb')
  result.each_line do |line|
    a = line.split.map! {|e| e.to_i}
    if a.reduce(:+) == i && a.all? {|e| is_prime(e)}
      count += 1
    else
      w << (i - s + 1) #record the wrong line number
    end
    i += 1
  end
  result.close
end

if count == e - s + 1
  puts 'OK'
else
  puts 'The following line(s) of the result file are wrong:'
  puts w.join(', ')
end

[brianfry713]

That is AC code.

[academus]

That is AC code.

Thanks, I tried again. This time the judge agrees with me! What a weird!

[Shahidul.CSE]

I am getting TLE with bellow code. But I got accepted in this way in problem Golbach's Conjecture and Golbach's Conjecture(II). where to change?

Code: Select all

#include<stdio.h>
int isPrime(long num)
{
    long i;
    for(i=2;i<=num/i;i++)
        if(num%i==0)
            return 0;
    return 1;
}
int main()
{
   
    long i,k=1,j,prime[78600],n,a,b,c,d,op,from,to,m,l,p;
    for(i=2;i<=1000000;i++)
       if(isPrime(i)==1)
            prime[k++]=i;
    while(scanf("%ld",&n)&&n!=0)
    {
        if(n<8)
        {
            printf("Impossible.\n");
            continue;
        }
        a=b=c=d=0;
         for(i=1;i<k;i++)
         {
             if(prime[i]>=n)
                break;
              for(j=i;j<k;j++)
             {
                 if(prime[j]>=n)
                    break;
                 for(l=j;l<k;l++)
                 {
                     if(prime[l]>=n)
                        break;
                    op=n-prime[i]-prime[j]-prime[l];
                    from=l;
                    to=k;
                    while(from<to)
                    {
                        m=(from+to)/2;
                        if(op>prime[m])
                            from=m+1;
                        else if(op==prime[m])
                        {
                            from=m;
                            break;
                        }
                        else if(op<prime[m])
                            to=m;

                    }
                    if(prime[from]==op)
                    {
                        a=prime[i];
                        b=prime[j];
                        c=prime[l];
                        d=prime[from];
                        break;
                    }
                }
                if(a+b+c+d==n)
                    break;
             }
             if(a+b+c+d==n)
                break;
        }
        if(a+b+c+d==0)
            printf("%ld %ld %ld %ld\n",a,b,c,d);
        else
            printf("Impossible.\n");



    }
    return 0;
}

[lighted]

Hints

There can be multiple solutions. Any good solution will be accepted.

Every even number >= 4 can be written as the sum of two primes

Taking into account hints above this problem can be reduced to following

If N < 8 answer = impossible
if N is even answer = 2 + 2 + (N - 4). (N - 4) is even so it can be expressed as sum of 2 primes.
if N is odd answer = 2 + 3 + (N - 5). (N - 5) is even so it can be expressed as sum of 2 primes.

You could also read this thread carefully and optimize your code applying Dominik Michniewski hints.