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?
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.felix-halim.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.felix-halim.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) + 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);
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 (N-4) or (N-5), 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) + 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
-
- 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;
}
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