11466 - Largest Prime Divisor

[roger12345]

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]

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

[PromeNabid]

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]

The program generates correct output but gets WA please help ..

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]

Doesn't match the sample I/O.

[মেহেদী সবুজ]

Code: Select all

Remove After Accepted

[alimbubt]

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