11466 - Largest Prime Divisor

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

Moderator: Board moderators

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

11466 - Largest Prime Divisor

Post by skinnyguy » Sat Jul 12, 2008 10:55 pm

are there any trick cases for this problem?
i make a sieve of 10 million and use this to factorise the number.
i also count how many factors there are of the number. such as for 32, there is 1 factor only so i output -1

but this kept giving me wrong answer during the contest.

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

Re: 11466 - Largest Prime Divisor

Post by Victor Barinov » Sat Jul 12, 2008 11:00 pm

There are nothing in problem statement about sign of numbers. So I think they can be negative...

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11466 - Largest Prime Divisor

Post by Robert Gerbicz » Sat Jul 12, 2008 11:26 pm

Another critical input: if n=1 or n=-1 then you should also print -1.

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

Re: 11466 - Largest Prime Divisor

Post by skinnyguy » Sat Jul 12, 2008 11:28 pm

:) thanks, i got AC now.
it was very unobvious to me that the numbers could be negative but the definition divisibility seems to fit perfectly well to them too.

wish i could have found that during the contest though..

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11466 - Largest Prime Divisor

Post by andmej » Sat Jul 12, 2008 11:34 pm

Also, I was getting Time Limit Exceeded. I got Accepted when I memoized input numbers so I wouldn't have to calculate any result more than once.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11466 - Largest Prime Divisor

Post by sapnil » Sun Jul 13, 2008 6:22 am

I'm getting WR plz help me. Here is my code

Code: Select all


...... Removed

Thanks
Last edited by sapnil on Sun Jul 13, 2008 8:53 pm, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11466 - Largest Prime Divisor

Post by mmonish » Sun Jul 13, 2008 6:49 am

>>sapnil
An integer number n is divisible by another integer number m if there is an integer t such that mt=n.
read this statement carefully and then think about negetive numbers..

hope this helps..

meghnal
New poster
Posts: 1
Joined: Sun Nov 25, 2007 5:13 pm

Re: 11466 - Largest Prime Divisor

Post by meghnal » Fri Oct 03, 2008 11:03 pm

Hi,
Can someone please give some test cases....i am getting wrong answer :(
I tried with following cases:
32: -1 (as only prime factor is 2)
-32: 2 (not sure what the output should be but i tried uploading with 2 as well as -1).
1 or -1: -1
Any prime number: -1

fahmi
New poster
Posts: 7
Joined: Sat Nov 22, 2008 9:10 am

Re: 11466 - Largest Prime Divisor

Post by fahmi » Sat Jan 10, 2009 4:43 pm

pllzzzz help..y i m getting WA.i cant fix d d problm with my code.plz som1 help :(
Fahmi

Code: Select all

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

long long a[100000],c,flag[1000000];

void seive(int n)
{
	long long k,i,j,r;
	k=sqrt(n);
	for(i=1;i<=n;i++)
		flag[i]=0;
	flag[1]=1;
	a[0]=2;
	c=1;
	for(i=4;i<=n;i+=2)
		flag[i]=1;
	for(i=3;i<=n;i+=2)
	{
		if(flag[i]==0)
		{
			a[c++]=i;
			if(k>=i)
			{
				r=i+i;
				for(j=i*i;j<=n;j+=r)
					flag[j]=1;
			}
		}
	}
	a[c]=0;
}

int main()
{ 
	long long n,i,max,j;
	seive(1000000);
	while(scanf("%lld",&n)==1&&n!=0)
	{
		j=0;
		max=0;
		if(n==1||n==-1)
		{
			printf("-1\n");
			continue;
		}
		n=labs(n);
		for(i=0;i<c&&n>=a[i];)
		{
			if(n%a[i]==0)
			{
				n=n/a[i];
				if(a[i]>max)
				{
					max=a[i];
					j++;
				}
			}
			else
			{
				i++;
			}
		}
		if(j==1)
			printf("-1\n");
		else printf("%lld\n",max);
	}
	return 0;
}

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11466 - Largest Prime Divisor

Post by sapnil » Tue Jan 20, 2009 7:24 pm

You use prime factorization here.
For factoring n, you need all primes <= sqrt(n).
sqrt( 14digit ) = 1e7.
But your code only generate primes with in 1e6.
Edit here....

Thanks.
Jony
"Dream Is The Key To Success"

@@@ Jony @@@

wasir_cse
New poster
Posts: 1
Joined: Sun Jul 19, 2009 2:12 pm

Re: 11466 - Largest Prime Divisor

Post by wasir_cse » Sun Jul 19, 2009 2:29 pm

// Why i got "RE" . Any one can help me please. //




#include<stdio.h>
#include<math.h>
#define N 10000000
_int64 a[N];
void seive()
{
_int64 i,j,s;
a[0]=0;a[1]=0;a[2]=1;

for(i=3;i<N;i=i+2)
{
a=1;a[i+1]=0;
}
s=long(sqrt(N));
for(i=3;i<=s;i=i+2)
if(a)
{
for(j=i*i;j<N;j+=i)
a[j]=0;
}


}

int main()
{

seive();
_int64 max,count,n,i;
while(scanf("%I64d",&n)==1&&n)
{
count=0;max=0;
for(i=2;i<=n/2+1;i++)
if(a)
{
if(n%i==0)
if(max<=i)
{
max=i;
count++;
}
}
if(count>1)
printf("%I64d\n",max);
else
printf("-1\n");
}
return 0;
}

lionking
New poster
Posts: 9
Joined: Tue Feb 17, 2009 6:46 pm

Re: 11466 - Largest Prime Divisor

Post by lionking » Sat Aug 08, 2009 3:29 pm

wasir_cse wrote:// Why i got "RE" . Any one can help me please. //
I think your problem similar to mine.

the size of prime array is too large to be allocated!

But I have not yet solve it.

Could someone help us?

fR0D
New poster
Posts: 29
Joined: Mon Feb 11, 2008 5:59 am
Contact:

Re: 11466 - Largest Prime Divisor

Post by fR0D » Sun Sep 12, 2010 8:52 am

Can anyone please guide me as to what is wrong in my code. It seems to give correct solution for all cases that i tried.

Code: Select all

Got AC. 
my bad. i thought we had to display -1 only for prime numbers.

gtcoder
New poster
Posts: 12
Joined: Tue Mar 23, 2010 5:45 am

Re: 11466 - Largest Prime Divisor

Post by gtcoder » Sun Feb 27, 2011 3:51 pm

I've been gulping loads of WAs on this. I've read about negative numbers and have handled them in both the ways that I've seen on uvatookit.com and another blog. But still can't figure the problem out.
I do a sieve till 10000000 then store all primes. Keep on dividing the given number the list ends or the number becomes 1.
If the number is negative or it becomes 1, I print the last prime that divided it.
Else I print the remaining part of the number.
But if divisor count is less than 2 I simply print -1.


:D (I heard somewhere that you should always keep your sunny side up).

Code: Select all

Got Accepted
EDIT: For those of you who might someday feel extremely helpless with this one.
1. Negative numbers have no problem just make them positive and do what you normally do.
2. If the number is a result of multiplying two primes and one of them is missing in you collection then the decision making needs a care.
If not fully divided then check if it was divided by any prime in your collection. If so, you have two primes, one in collection and one in hand. That's where I made my mistake.

A good Sample is 99999999999997 which should give 119189511323 not -1.

Thanks to mmonish, wasn't getting your point at first buddy.

kushol
New poster
Posts: 4
Joined: Wed Jan 05, 2011 10:15 am

Re: 11466 - Largest Prime Divisor

Post by kushol » Tue Jun 14, 2011 8:12 pm

WHY WAAAAAAAAA???????????
For which value it is showing wrong ans........................ :oops:

Code: Select all

Removed
Last edited by kushol on Thu Dec 22, 2011 4:32 pm, edited 1 time in total.

Post Reply

Return to “Volume 114 (11400-11499)”