CDRSANJ - CODER FIRST PROBLEM
Coder Sanjay is now ready to put up his first problem in his favorite website SPOJ. As it is his first problem, he wanted it to be easy so that most of them could get an AC.
The problem statement looks like this:
F(x) is a function whose properties are as follows.
- F(x) = 0 at x = 0.
- F(x) = 1 at x = 1.
- F(x) = 2 at x = 2.
- F(x) = 0 if x is an odd prime.
- F(a*b) = F(a) + F(b), where a, b are two positive integers and sum of a and b is minimum.
Your task is simple. You are to output the value of F(x) for the given input integer x.
Input
The only line of input contains a single integer x (0 < x < 100001).
Output
Output the value of F(x).
Example
Input: 4 Output: 4
hide comments
Huan Zhou:
2018-05-16 11:20:45
Pretty interesting problem. But the tags are misleading -- just ignore them. |
|
dsri_99:
2017-12-20 16:49:21
I suggest not to see comments while solving this problem. It's a quite simple problem.But takes time for the idea to strike. |
|
utkarshsingh99:
2017-11-22 21:52:34
Quite easy. Nice usage of recursion.
|
|
yead_025:
2017-10-31 19:23:54
no need to use dp |
|
aman_9899:
2017-07-03 22:31:10
game of odd and even..!!!! |
|
sushanth_r:
2017-06-15 10:01:16
Numerous ways to solve this problem. 2 Naive Approaches, DP, Recursion.
|
|
imshubhamk:
2017-06-09 05:52:30
writing it on with pen n paper will get you logic in 2-3 min maybe less...
|
|
shahzada:
2017-03-10 13:34:30
take a pen and paper and observe the pattern |
|
govindgupta:
2017-01-13 13:36:50
My 100th on spoj :) |
|
cs_abhi2000:
2017-01-12 21:05:16
Nice one...
|
Added by: | verdu sanjay |
Date: | 2016-03-12 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: GOSU |