## 11466 - Largest Prime Divisor

Moderator: Board moderators

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

### 11466 - Largest Prime Divisor

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

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

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

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
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11466 - Largest Prime Divisor

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

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

>>sapnil
An integer number n is divisible by another integer number m if there is an integer t such that mt=n.

hope this helps..

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

### Re: 11466 - Largest Prime Divisor

Hi,
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

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

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

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

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

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

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
New poster
Posts: 4
Joined: Wed Jan 05, 2011 10:15 am

### Re: 11466 - Largest Prime Divisor

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

Code: Select all

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