FCDC - Factorial Modulo


You are given 2 integers a, b. Find the number of i for which i! is divisble by a but not b. if i! is divisible by a and b, then you should not count that i.

Input

One line that contains a and b.

Output

Output the result in one line.

Example

Input:
2 3

Output:
1

Constraints

 1 ≤ a ≤ b ≤ 107

Explanation

2! is the only factorial which is divisible by 2 and not divisible by 3.


hide comments
Pawe³ Ma¶luch: 2016-02-17 19:57:06

I've already submitted my solution and it turned out that we should consider only i! for i > 0.

Pawe³ Ma¶luch: 2016-01-17 20:44:54

Should we consider i! for i >=0 or for i > 0 ?

william: 2015-11-22 08:23:05

Last edit: 2015-11-22 09:00:13
pankaj: 2015-11-20 20:56:58

What will be the ans for following test cases
3 15
2 8
4 12

JY: 2015-11-17 08:25:57

Why have you kept the constraints too weak?
You could have given many test cases (maybe about 10^4) OR a and b of range about 10^12, and still it could have been solved in a second .

Ruhan Habib: 2015-11-17 06:45:56

A lot of submissions are trying to use too complicated methods... this can be solved easily without prime checking and stuffs. @Bhuvnesh: for the input 4 6 output should be 0.

Last edit: 2015-11-17 06:52:03
Bhuvnesh Jain: 2015-11-16 19:24:53

What is the answer when a=4 and b=6?

Prakhar Dev Gupta: 2015-11-13 18:37:08

@Lakshman: This problem is getting on my nerves now! I've tried so many timeS! already made 11 submissions! Should I not check for primality?

If I did it on simple approach and putting your testcase, still the time taken is way too large!
What else? :(

Last edit: 2015-11-13 18:44:21
[Lakshman]: 2015-11-13 15:18:33

@Prakhar why you are checking for prime multiple times. Think simple, here is one test case 1234345 5465667 your code is taking more than minute , however my python code gives output in 0.05s

Ruhan Habib: 2015-11-13 05:57:52

@[Lakshman]: the problem was meant to solve the way you solved it. My sample solution(the first submission) also used quite the same approach. :)


Added by:Ruhan Habib
Date:2015-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem