## 10168 - Summation of Four Primes

Moderator: Board moderators

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

### Re: 10168 - Summation of Four Primes

Thanks lighted !

So it seems that only for N<8 it is impossible otherwise there must be a solution.

Another thing is to find all prime upto 10000000, which is take times 10 sec. So isn't it possible to find any two prime for (N-4) or (N-5), within the primes upto 1000000 or 100000?
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

You don't need to find all primes in range [1..1e+7]. It is enough to find all primes in range [1..sqrt(1e+7)], there are about 1581 primes.

This prime numbers are necessary to check primality of any number in range [1..1e+7] by division method. If a number N is not divisible by any of that primes then it's a prime.

Code: Select all

``````int p[1600]; // primes in range [1..sqrt(1e+7)]

int cnt; // number of primes in range [1..sqrt(1e+7)]

int isPrime(int n) {

int q = sqrt(n) + 1e-8;

for (int i = 0; i < cnt  &&  p[i] <= q; i++)
if(n % p[i] == 0) return 0;

return n != 1;
}
``````

Code: Select all

``````a = 2;
b = 2 + n % 2;
n -= a + b;

if (n == 4) c = 2;
else
for (c = 3; 1; c += 2)
if (isPrime(c))
if (isPrime(n - c)) break;

printf("%d %d %d %d\n", a, b, c, n - c);``````
My program's runtime is 0.025.
Last edited by lighted on Sat Sep 20, 2014 4:55 pm, edited 2 times in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

### Re: 10168 - Summation of Four Primes

Shahidul.CSE wrote: Another thing is to find all prime upto 10000000, which is take times 10 sec. So isn't it possible to find any two prime for (N-4) or (N-5), within the primes upto 1000000 or 100000?
I checked your way and got accepted in 0.362. There are about 664579 primes in range [1..1e+7]. You should change your prime generating. I used sieve of eratosthenes.

Code: Select all

``````#define MAX 10000001

char sieve[MAX];

int p[664600];  // primes in range [1..1e+7]

int i, j, cnt, n, q = sqrt(MAX) + 1e-8;

int main() {

for (i = 3; i <= q; i += 2)
if(!sieve[i])
for (j = i * i; j < MAX; j += i) sieve[j] = 1;

p[0] = 2;

for (cnt = 1, i = 3; i < MAX; i += 2)
if (!sieve[i]) p[cnt++] = i;
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 10168 - Summation of Four Primes

Hii, I am getting WA for this problem. Plz tell me the bug in my code or give some critical inputs for this question:

Code: Select all

``````#include<cstdio>
#include<cstring>
using namespace std;
int prime[10000010];
int main()
{
memset(prime,1,sizeof(prime));
int i,j,a,b,diff,n,count;
for(i=2;i<=3163;i++)
{
if(prime[i])
for(j=i*i;j<=10000000;j=j+i)
prime[j]=0;
}
prime[0]=prime[1]=0;
while(scanf("%d",&n)!=EOF)
{
if(n<8)
{
printf("Impossible\n");
continue;
}
if(n==9)
{
printf("2 2 2 3\n");
continue;
}
if(n%2 == 0)
{
printf("2 2 ");
n=n-4;
}
else
{
printf("2 3 ");
n=n-5;
}
i=2;
while(i<=(n-i))
{
if(prime[i]&&prime[n-i])
{
printf("%d %d\n",i,n-i);
break;
}
i++;
}
}
return 0;
}
``````

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

### Re: 10168 - Summation of Four Primes

My advice to you -> always copy/paste output format from sample or problem description.

Correct Output

Code: Select all

``Impossible.``

Code: Select all

``Impossible``
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 10168 - Summation of Four Primes

Thanx . Got accepted.

But its run time is 0.652s. Can u tell me what changes I should make in my code so that the run time is less?

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

### Re: 10168 - Summation of Four Primes

I sent you PM.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman