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 (N4) or (N5), within the primes upto 1000000 or 100000?
10168  Summation of Four Primes
Moderator: Board moderators

 Experienced poster
 Posts: 148
 Joined: Sun Jul 13, 2014 4:32 am
 Location: Rangpur, Bangladesh
Re: 10168  Summation of Four Primes
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felixhalim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felixhalim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com
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.
My program's runtime is 0.025.
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) + 1e8;
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);
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
Re: 10168  Summation of Four Primes
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.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 (N4) or (N5), within the primes upto 1000000 or 100000?
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) + 1e8;
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

 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=n4;
}
else
{
printf("2 3 ");
n=n5;
}
i=2;
while(i<=(ni))
{
if(prime[i]&&prime[ni])
{
printf("%d %d\n",i,ni);
break;
}
i++;
}
}
return 0;
}
Re: 10168  Summation of Four Primes
My advice to you > always copy/paste output format from sample or problem description.
Correct OutputYour Output
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

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