11466 - Largest Prime Divisor

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

[Victor Barinov]

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

[Robert Gerbicz]

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

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

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

[sapnil]

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

Code: Select all

...... Removed

Thanks

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

[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

[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;
}

[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

[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;
}

[lionking]

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

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]

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.

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

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

Code: Select all

Removed