## 10168 - Summation of Four Primes

Moderator: Board moderators

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

### Re: 10168 - Summation of Four Primes

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

rafay-hasan
New poster
Posts: 4
Joined: Sat Jul 03, 2010 1:04 pm

### Re: 10168 - Summation of Four Primes

#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

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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10168 - Summation of Four Primes

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

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

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

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

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

Thanks, very much. Resubmitted and got accepted now.

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

### Incorrect judge for problem 10168: Summation of Four Primes

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

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

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

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

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

### Re: 10168 - Summation of Four Primes

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,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
Email me: shahidul.cse.brur@gmail.com

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

### Re: 10168 - Summation of Four Primes

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.