Page 1 of 2

11466 - Largest Prime Divisor

Posted: Sat Jul 12, 2008 10:55 pm
by skinnyguy
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.

Re: 11466 - Largest Prime Divisor

Posted: Sat Jul 12, 2008 11:00 pm
by Victor Barinov
There are nothing in problem statement about sign of numbers. So I think they can be negative...

Re: 11466 - Largest Prime Divisor

Posted: Sat Jul 12, 2008 11:26 pm
by Robert Gerbicz
Another critical input: if n=1 or n=-1 then you should also print -1.

Re: 11466 - Largest Prime Divisor

Posted: Sat Jul 12, 2008 11:28 pm
by skinnyguy
:) 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..

Re: 11466 - Largest Prime Divisor

Posted: Sat Jul 12, 2008 11:34 pm
by andmej
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.

Re: 11466 - Largest Prime Divisor

Posted: Sun Jul 13, 2008 6:22 am
by sapnil
I'm getting WR plz help me. Here is my code

Code: Select all


...... Removed

Thanks

Re: 11466 - Largest Prime Divisor

Posted: Sun Jul 13, 2008 6:49 am
by mmonish
>>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..

Re: 11466 - Largest Prime Divisor

Posted: Fri Oct 03, 2008 11:03 pm
by meghnal
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

Re: 11466 - Largest Prime Divisor

Posted: Sat Jan 10, 2009 4:43 pm
by fahmi
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;
}

Re: 11466 - Largest Prime Divisor

Posted: Tue Jan 20, 2009 7:24 pm
by sapnil
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

Re: 11466 - Largest Prime Divisor

Posted: Sun Jul 19, 2009 2:29 pm
by wasir_cse
// 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;
}

Re: 11466 - Largest Prime Divisor

Posted: Sat Aug 08, 2009 3:29 pm
by lionking
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?

Re: 11466 - Largest Prime Divisor

Posted: Sun Sep 12, 2010 8:52 am
by fR0D
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.

Re: 11466 - Largest Prime Divisor

Posted: Sun Feb 27, 2011 3:51 pm
by gtcoder
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.

Re: 11466 - Largest Prime Divisor

Posted: Tue Jun 14, 2011 8:12 pm
by kushol
WHY WAAAAAAAAA???????????
For which value it is showing wrong ans........................ :oops:

Code: Select all

Removed