CDRSANJ - CODER FIRST PROBLEM


 

<strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p>
<strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p><strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p><strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p><strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p><strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p><strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p>
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p><strong>CODER SANJAY</strong> is now ready to put up his first problem in his favorrite website <strong>SPOJ</strong>.As it is his first problem,he wanted it to be easy so that most of them could get an <strong>AC</strong>.
The problem statement looks like this:
<p>
<br><strong>F(x)</strong> is a function whose properties are as follows.</br>
<p>1.<strong>F(x)=0</strong> at x=0.</p>
<p>2.<strong>F(x)=1</strong> at x=1.</p>
<p>3.<strong>F(x)=2</strong> at x=2.</p>
<p>4.<strong>F(x)=0</strong> if x is odd prime.</p>
<p>5.<strong>F(ab)=F(a)+F(b)</strong>,where a,b are two positive integers and sum of a and b is minimum.</br>
</p>
<br>Your task is simple.You are to output the value of <strong>F(x)</strong> for the given input integer <strong>x</strong>. </br>
Input
The only line of input contains a single integer <strong>x</strong>. 
Output
Output the value of <strong>F(x)</strong>
Example
Input:
<p>
4
</p>
Output:
<p>
4
</p>

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.

 

CONSTRAINSTS:

0 < x < 100001.

Input

The only line of input contains a single integer x

Output

Output the value of F(x).


Example

Input:

4

Output:

4


hide comments
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...
try these testcases:-
input: 256 48 100000
output: 16 8 10

abhaypandey: 2016-12-22 04:19:51

just two lines of code

aditya_rev: 2016-11-04 04:02:25

nice recurtion problem. enjoying to solve it :)

ftnovac: 2016-09-24 11:28:37

Be careful with test cases like:
Input: 128 256 512
Output: 14 16 18

No need to use any fancy algorithm (Sieve).

Last edit: 2016-09-24 11:29:39
rishabh_nitw: 2016-08-10 15:49:27

NO need to use DP bcz problm contains only one test case case and no sub problem will repeat. :)

vinay12345: 2016-08-05 17:02:52

no use of sieve no use of anything only use 2 to find answer ......haha

bais_hariom: 2016-07-31 20:33:34

Nice Problem! #DP and #Recursion


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