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.
1.F(x)=0 at x=0.
2.F(x)=1 at x=1.
3.F(x)=2 at x=2.
4.F(x)=0 if x is odd prime.
5.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.
0 < x < 100001.
The only line of input contains a single integer x.
Output the value of F(x).
Be careful with test cases like:
NO need to use DP bcz problm contains only one test case case and no sub problem will repeat. :)
no use of sieve no use of anything only use 2 to find answer ......haha
Nice Problem! #DP and #Recursion
easy rec :)
This is a basic problem...so who haven't solved more than 30 problems can give this a try!!!
nice one.. AC in 2nd.
Murad Al Wajed:
nice problem. ac in 1
This is a beautiful problem especially if you try to prove why our method gives minimun answer. You dont have to dig into sieve and store prime numbers . Concentrate on Pattern and above all try to prove things by induction. Your solution should work even if x is 10^19 (Ideally speaking!!).Last edit: 2016-04-22 16:34:13