10168 - Summation of Four Primes

[Shahidul.CSE]

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?

[lighted]

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.

[lighted]

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;

[richatibrewal]

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]

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

Correct Output

Code: Select all

Impossible.

Your Output

Code: Select all

Impossible

[richatibrewal]

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]

I sent you PM.