10948 - The primary problem

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10948 - The primary problem

Post by Obaida » Thu May 08, 2008 1:05 pm

Code: Select all

Accepted now. But it takes so much time could any one give me a better formula.  
try_try_try_try_&&&_try@try.com
This may be the address of success.

yeasin_acm_solver
New poster
Posts: 11
Joined: Wed Jun 09, 2010 2:30 pm
Location: University Of Science & Technology Chittagong (USTC) Bangladesh

Re: 10948 - The primary problem

Post by yeasin_acm_solver » Sat Jan 22, 2011 10:54 pm

Accepted
Last edited by yeasin_acm_solver on Thu Feb 03, 2011 12:42 am, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 10948 - The primary problem

Post by helloneo » Wed Jan 26, 2011 6:17 pm

Try this input

Code: Select all

101
My output is..

Code: Select all

101:
NO WAY!

Hope this help :)

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10948 - The primary problem

Post by DD » Thu Mar 17, 2011 7:38 am

I just wonder that how those people who got 0.00 for this problem? Even they build prime table before, they two sum problem still need O(N) time by implementing hash. Really curious about this. :o
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

saiful_islam
New poster
Posts: 6
Joined: Tue Feb 08, 2011 7:41 pm

Re: 10948 - The primary problem

Post by saiful_islam » Sat May 05, 2012 8:27 am

Code: Select all

#include<stdio.h>
#define MAX 1000000
#define MAXH MAX/2

char pr[MAX/16+10];
int a[78599];

void seive()
{
    int l=1090,i,j;
    for(i=3;i<l;i +=2)
    {

        if(!(pr[i>>4]&(1<<((i>>1)&0x7))))
        {
            for(j=i*i/2;j<=MAXH;j +=i)
            pr[j>>3] |=(1<<(j&0x7));
        }
    }
}
void isprime()
{
    register int i,p=1;
    a[0]=2;
   for(i=3;i<=99993;i++)
   {
        if(!(pr[i>>4]&(1<<((i>>1)&0x7))))
        {
            a[p]=i;
			p++;
        }
    i++;
   }
}
int find ( int target, int first, int last)
{
    int mid;
	if (first > last)
		return -1;

	 mid = (first + last) / 2;
		if (a[mid]==target)
			return mid;

	if (a[mid]<target)
			return find( target, mid+1, last);

	return find(target, first, mid-1);

}
int main()
{
    int i,j,k,l,n,m;
    seive();
    isprime();

    while(scanf("%d",&n)&&n)
    {
        printf("%d:\n",n);
        if(n%2)
        {
            m= n-2;
            if(find(m, 0, 78498)>=0)
            {
                printf("2+%d",a[find(m, 0, 78498)]);
            }
            else
            printf("NO WAY!");
        }
        else
        {
            for(i=0;i+1;i++)
            {
                m = n-a[i];
                if(find(m, 0, 78498)>=0)
                {
                    printf("%d+%d",a[i],a[find(m, 0, 78498)]);
                    break;
                }
            }
        }
        printf("\n");
    }
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10948 - The primary problem

Post by brianfry713 » Tue May 08, 2012 12:04 am

Missing a 9 on line 25.
Check input and AC output for thousands of problems on uDebug!

alexiago
New poster
Posts: 14
Joined: Thu Jan 24, 2008 6:34 pm

Re: 10948 - The primary problem

Post by alexiago » Thu Aug 01, 2013 10:38 pm

I solved this problem by creating an array and a SET with all primes up to 1 million. I looped thru the array getting the difference between the number N that we are looking for and the prime (i.e. N - primes), if we have that difference in the SET we found our sum and print it.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10948 - The primary problem

Post by brianfry713 » Tue Dec 03, 2013 3:09 am

If you resubmit you'll get TLE. Read this thread.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10948 - The primary problem

Post by uDebug » Thu May 01, 2014 9:07 am

Cho wrote:Nothing tricky, just some boundary cases:
Thanks for these great test cases.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10948 - The primary problem

Post by uDebug » Thu May 01, 2014 9:11 am

alexiago wrote:I solved this problem by creating an array and a SET with all primes up to 1 million. I looped thru the array getting the difference between the number N that we are looking for and the prime (i.e. N - primes), if we have that difference in the SET we found our sum and print it.

This problem's almost identical to 543 - Goldbach's Conjecture. If you're having issues, try that problem first and then give this one a shot.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

battirunner
New poster
Posts: 14
Joined: Fri Aug 15, 2014 3:48 pm

Re: 10948 - The primary problem

Post by battirunner » Sun Aug 24, 2014 1:05 am

i have test for all kind of possible case but still getting WA. need some help with tricky test case
here is my code
#include<stdio.h>
#include<cstdio>
int p=0;
int prm[136]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769};
int prime[1000005];
void primecheck()
{
int f;
for(int i=2;i<=1000005;i++)
{
f=0;
for(int j=0;j<136;j++)
{
if(i%prm[j]==0&&i!=prm[j])
{
f=1;
break;
}
}

if(f==0)
{
prime[p]=i;
p++;
}

}

p=0;


}
int main()
{

int n,a=1,f=0,t,flag=0,u=0,l=0;
primecheck();
while(1)
{

scanf("%d",&n);

if(n==0)
break;
t=n;
a=1;
printf("%d:\n",n);

for(int s=0;s<80000;s++)
{
if(prime[s]>=n)
{
p=s;
break;
}
}
u=p-1;
l=0;

while((u-l)>=0)
{

if(prime[l]+prime==n)
{
printf("%d+%d\n",prime[l],prime);
f=1;
break;
}
if(prime[l]+prime>n)
u--;

if(prime[l]+prime<n)
l++;
}


if(f==0)
printf("NO WAY!\n");
f=0;

}

return 0;
}

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

Re: 10948 - The primary problem

Post by lighted » Tue Aug 26, 2014 7:22 pm

Your prime checking is wrong for numbers greater than 769 * 769. You must add to your prm arrary all primes less than 1000 to check primality of numbers less than million. :)

Input

Code: Select all

982084
0
Acc Output

Code: Select all

982084:
17+982067
Your Output

Code: Select all

982084:
3+982081
982081 is not a prime. 982081 = 991 * 991. :)

Use code tags. Don't forget to remove your code after getting accepted. 8)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

samir_h
New poster
Posts: 11
Joined: Wed Mar 18, 2015 8:47 am

Re: 10948 - The primary problem

Post by samir_h » Sat Nov 07, 2015 6:15 am

Obaida wrote:

Code: Select all

Accepted now. But it takes so much time could any one give me a better formula.  
@Obaida: The trick is generating/detecting prime numbers.

Post Reply

Return to “Volume 109 (10900-10999)”