## 11466 - Largest Prime Divisor

Moderator: Board moderators

roger12345
New poster
Posts: 3
Joined: Tue Feb 01, 2011 5:40 am

### Re: 11466 - Largest Prime Divisor

Help me please im gettins time limit, the input 99999999999997 doesnt finish :S

Code: Select all

``AC NOW``
EDIT: My sieve was too slow

shaon_cse_cu08
New poster
Posts: 50
Joined: Tue May 25, 2010 9:10 am
Contact:

### Re: 11466 - Largest Prime Divisor

I use my own prime factorization function... this is Child's math... divide a number a number until it can't be divided... dan increment it by 2..bcoz all primes except for 2 are odd... and my code gave me 0.032 s... It would b more faster if i use only da prime... but sometimes Simplicity is more fun dan complexity

Code: Select all

``````#include<stdio.h>
int main()
{
int i,n;

while(scanf("%d",&n)!=EOF)
{
while(n%2==0)
{
printf("2 ");
n/=2;
}

for(i=3;i*i<=n;)
{
if(n%i==0)
{
n=n/i;
printf("%d ",i);
}
else
i+=2;
}
if(n>1)
printf("%d\n",n);
}
return 0;
}``````
I'll keep holding on...Until the walls come tumbling down...And freedom is all around .....

PromeNabid
New poster
Posts: 21
Joined: Mon Jun 18, 2012 12:52 am
Contact:

### Re: 11466 - Largest Prime Divisor

Some sample I/O for this problem.
Input:

Code: Select all

``````1
-1
1111111111111
12345678910121
12345678910121
1234567891012
99999999999997
0``````
Output:

Code: Select all

``````-1
-1
265371653
173882801551
173882801551
4281283
119189511323``````

masri77
New poster
Posts: 1
Joined: Wed Jul 18, 2012 3:32 am

### Re: 11466 - Largest Prime Divisor

Code: Select all

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

int main() {
long long int num, ans;
long long int i;

while (scanf("%lld", &num) && num != 0) {
if (num < 0)
num *= -1;

ans = num;

while (ans % 2 == 0)
ans /= 2;

i = 3;
while (i * i <= ans) {
if (ans % i == 0)
ans /= i;
else
i += 2;
}
printf("%lld\n", num == ans ? -1 : ans);
}
return 0;
}
``````

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

### Re: 11466 - Largest Prime Divisor

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm

### Re: 11466 - Largest Prime Divisor

Code: Select all

``Remove After Accepted``

alimbubt
New poster
Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm
Contact:

### Re: 11466 - Largest Prime Divisor

For this problem, Some important notes are...
1) What will happen when there exists less than 2 prime divisors.
2) What will happen when the input is less than 0.

Some Input-Output:
Input:

Code: Select all

``````1000
20
32
1
-1
-10
61536575712
8172385155
90090
12
199900
-26356
-32
8748234
23462482
23457826407
234872648001
436598
345387
2347
17
37
0
``````
Output:

Code: Select all

``````5
5
-1
-1
-1
5
324889
16509869
13
3
1999
599
-1
113
690073
77418569
348559
521
16447
-1
-1
-1
``````
Give me six hours to chop down a tree and I will spend the first four sharpening the axe...(BUBT ILLUSION)
http://uhunt.felix-halim.net/id/155497
http://onlyprogramming.wordpress.com/

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

### uva 11466

cant find my bug !!!

Code: Select all

``````#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#define max 10000500
using namespace std;
vector <long long> prime;
bool flag[max];

void sieve()
{

prime.push_back(2);
//cout<<"h;;";
for(long long i=4;i<max;i+=2)
flag[i]=true;
for(long long i=3;i<max;i+=2)
{
if(!flag[i])
{
prime.push_back(i);
if(max/i>=i)
{
flag[j]=true;
}

}
}

}
int main()
{
long long x;
sieve();
while(cin>>x && x)
{
long long m=x;
if(x<0)
x=-x;
long long int flag=0,dlx=0;
for(int i=0;prime[i]<max;i++)
{

flag=0;
while(x%prime[i]==0)
{
x=x/prime[i];
if(prime[i]>dlx)
dlx=prime[i];
}
for(long long l=i;prime[l]<=(long long)sqrt(x);l++)
{
if(x%prime[l]==0)
{
flag=2;
i=l-1;
break;

}

}
if(flag==0)
{
if(x>dlx)
dlx=x;
break;

}

}
if(dlx==0 || dlx==m)
cout<<"-1"<<endl;
else
cout<<dlx<<endl;

}

return 0;
}

``````

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

### Re: uva 11466

Input 4 output should be -1
Check input and AC output for thousands of problems on uDebug!

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

### uva 11466

removed after getting accepted
Last edited by ashdboss on Tue Dec 10, 2013 2:50 pm, edited 1 time in total.

t.tahasin
New poster
Posts: 38
Joined: Tue May 28, 2013 11:21 pm

### Re: uva 11466

Input:
-21
-22
0

Output:
7
11

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

### Re: uva 11466

Thanks...got AC

saniatrasel
New poster
Posts: 5
Joined: Tue Apr 07, 2015 11:10 am

### Re: 11466 - Largest Prime Divisor

I get WA of the below code... Though all sample inputs are successfully generate desired output.
But still I get WA from UVa. Here is the below code:

Code: Select all

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

int main()
{
long long num;
int count = 0;
while((scanf("%lld",&num))&&(num!=0))
{
long long int i;
count = 0;
if(num<0)
num = num *-1;
for(i=2;i<=sqrt((double)num);i++)
{
while((num%i==0)&&(i!=num))
{
num = num/i;
count++;
}
if(num<i)
break;
}
if(count>0)
printf("%lld\n",num);
else
printf("%d\n",-1);
}
}``````

papon sen
New poster
Posts: 1
Joined: Mon Nov 16, 2015 9:39 pm

### Re: 11466 - Largest Prime Divisor

The program generates correct output but gets wrong ans. I tried it for each input which is given.Please help me to find why my code is getting wrong answer.

Code: Select all

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,input;
while(scanf("%lld",&input)!=EOF)
{

if(input==0)
break;
if(input<0)
input*=(-1);
n=input;
long long int counter=2;
long long int largest;
while(counter*counter<=n)
{

if(n%counter==0)
{
n=n/counter;
largest=counter;
}
else{
if(counter==2)
counter=3;
else
counter+=2;

}
}
if(n>=counter)
{
largest=n;
}
if(largest==2 || largest==input||input==1)
{
largest=-1;
}
printf("%lld\n",largest);
}
return 0;
}
``````

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

### Re: 11466 - Largest Prime Divisor

Input

Code: Select all

``````9
0``````
Correct output

Code: Select all

``-1``
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman