## 11466 - Largest Prime Divisor

Moderator: Board moderators

### 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
roger12345
New poster

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

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

shaon_cse_cu08
New poster

Posts: 50
Joined: Tue May 25, 2010 9:10 am

### Re: 11466 - Largest Prime Divisor

Some sample I/O for this problem.
Input:
Code: Select all
`1-1111111111111112345678910121123456789101211234567891012999999999999970`

Output:
Code: Select all
`-1-12653716531738828015511738828015514281283119189511323`
PromeNabid
New poster

Posts: 13
Joined: Mon Jun 18, 2012 12:52 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;}`
masri77
New poster

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

### Re: 11466 - Largest Prime Divisor

Doesn't match the sample I/O.
brianfry713
Guru

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

### Re: 11466 - Largest Prime Divisor

Code: Select all
`Remove After Accepted`
মেহেদী সবুজ
New poster

Posts: 6
Joined: Tue Apr 03, 2012 2:34 pm

### 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
`100020321-1-106153657571281723851559009012199900-26356-3287482342346248223457826407234872648001436598345387234717370`

Output:
Code: Select all
`55-1-1-15324889165098691331999599-11136900737741856934855952116447-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/
alimbubt
New poster

Posts: 39
Joined: Tue Aug 07, 2012 10:40 pm