10168 - Summation of Four Primes

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

samin_yasar
New poster
Posts: 5
Joined: Sat Mar 28, 2009 6:15 pm

Re: 10168 - Summation of Four Primes

Post by samin_yasar » Fri Apr 03, 2009 9:07 pm

#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
New poster
Posts: 4
Joined: Sat Jul 03, 2010 1:04 pm

Re: 10168 - Summation of Four Primes

Post by rafay-hasan » Wed Dec 08, 2010 3:47 pm

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
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: 10168 - Summation of Four Primes

Post by shantanu18 » Tue Jun 21, 2011 10:55 am

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;
}

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10168 - Summation of Four Primes

Post by plamplam » Sat Aug 13, 2011 3:30 pm

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 :) :wink:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Karcher
New poster
Posts: 2
Joined: Fri Nov 04, 2011 10:42 am

Re: 10168 - Summation of Four Primes

Post by Karcher » Fri Nov 04, 2011 10:50 am

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
New poster
Posts: 7
Joined: Thu Oct 25, 2012 11:42 pm

Re: 10168 - Summation of Four Primes-PE

Post by Caren » Fri Oct 26, 2012 12:06 am

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
Last edited by Caren on Sat Oct 27, 2012 12:18 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10168 - Summation of Four Primes

Post by brianfry713 » Fri Oct 26, 2012 12:20 am

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.
Check input and AC output for thousands of problems on uDebug!

Caren
New poster
Posts: 7
Joined: Thu Oct 25, 2012 11:42 pm

Re: 10168 - Summation of Four Primes

Post by Caren » Fri Oct 26, 2012 10:01 am

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

Code: Select all

AC

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10168 - Summation of Four Primes

Post by brianfry713 » Sat Oct 27, 2012 12:20 am

Resubmit, the judge wasn't working but is now fixed.
Check input and AC output for thousands of problems on uDebug!

Caren
New poster
Posts: 7
Joined: Thu Oct 25, 2012 11:42 pm

Re: 10168 - Summation of Four Primes

Post by Caren » Sat Oct 27, 2012 12:35 am

Thanks, very much. Resubmitted and got accepted now.

academus
New poster
Posts: 3
Joined: Sat Jun 22, 2013 3:58 pm

Incorrect judge for problem 10168: Summation of Four Primes

Post by academus » Sat Jun 22, 2013 4:21 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Incorrect judge for problem 10168: Summation of Four Pri

Post by brianfry713 » Tue Jun 25, 2013 12:29 am

That is AC code.
Check input and AC output for thousands of problems on uDebug!

academus
New poster
Posts: 3
Joined: Sat Jun 22, 2013 3:58 pm

Re: Incorrect judge for problem 10168: Summation of Four Pri

Post by academus » Tue Jun 25, 2013 6:26 am

brianfry713 wrote:That is AC code.
Thanks, I tried again. This time the judge agrees with me! What a weird!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh
Contact:

Re: 10168 - Summation of Four Primes

Post by Shahidul.CSE » Fri Sep 19, 2014 9:10 pm

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;
}
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10168 - Summation of Four Primes

Post by lighted » Sat Sep 20, 2014 12:11 pm

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest