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

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 » Sat Sep 20, 2014 1:58 pm

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
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 4:20 pm

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: 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 4:43 pm

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

Post by richatibrewal » Sat Nov 08, 2014 5:22 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10168 - Summation of Four Primes

Post by lighted » Sat Nov 08, 2014 6:03 pm

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

Post by richatibrewal » Sat Nov 08, 2014 7:56 pm

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10168 - Summation of Four Primes

Post by lighted » Sun Nov 09, 2014 2:00 pm

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

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest