Super Factor Sum

Problem code: FACTSUM

All submissions for this problem are available.

Given a positive integer K > 2, with prime
factorization:

K = p1^a1 * p2^a2 ... * pn^an

Compute the following:

S = a1*p1 + a2*p2 ... + an*pn.

Input

A list of <100 integers, one on each line, all less than 2*10^19.

Output

For each integer compute the super factor sum and output it on a single line.

Example

Input:
6
7
Output:
5
7

Author: admin
Date Added: 1-12-2008
Time Limit: 30 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

johnny22smart @ 1 Jul 2009 04:34 PM

How do you get this working? My perfect solution can correctly scan in the numbers, but it never seems to finish. On my computer, 10 million numbers can run in less than 1 sec

i0exception @ 1 Jul 2009 05:41 PM

@Johnny The numbers can be as large as 2 X 10 ^ 19. That is much much larger than 10 million.

johnny22smart @ 2 Jul 2009 10:06 AM

I meant i can input the numbers 1- 10 million and it will run in less than one sec. The problem with my code is that my prime factorizor takes sqrt(n)/6 time, which when inputing a 19 digit prime is too slow.

i0exception @ 2 Jul 2009 05:26 PM

@Johnny Then you need to find a more efficient algorithm :)

atulsingh_jan @ 10 Jul 2009 02:28 AM

I think there is a mistake in formula of " K=p1^a1*p2^a2*.....*pn^an ", it should be " K=p1^a1 p2^a2 ..... pn^an ".
Because if first formula is correct then the output of 6(=2^1*3^1) will be 2(1^2 1^3) but output is given 5.
According to second formula 6(=2^2 2^1) and output is 5(=2^2 1^2).

atulsingh_jan @ 10 Jul 2009 02:30 AM

space in the above comment is addition sign which is not showing if I wrote addition sign ( )

i0exception @ 10 Jul 2009 02:39 AM

The one with the multiplication is the representation of the value as a product of its prime factors while what you have to compute is also specified in the statement and is different from the prime factorization that you mention. Read the statement carefully.

how do we know when to stop

ysubmarine @ 7 Dec 2011 12:45 AM
how do we know when to stop taking inputs, that is what is the condition when input list is done. I assumed that when the user inputs 0, I can begin showing the output...

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions