Distinct Prime Factors

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type
Maniacal Midsummer Marathon 2014 by AL, TL, JJ

"What do we make them do for problem A?"
"Uh… make them prime factorize a number."
"Isn't that a bit too easy?"
"Fine, make them prime factorize a BIG number."
"Like with GNFS? Isn't that a bit too hard?"
"Fine, let's make them prime factorize a lot of numbers."
"Just how many are you thinking?"
"All of them."
"wat."
"k screw this, let's slap on some bounds and call it a day."

Given two integers A and B (2 \le A \le B \le 1\,000\,000), determine the number of distinct prime factors for each integer between A and B, inclusive.

Input Specification

The input consists of two lines. The first line will contain the integer A, and the second line will contain the integer B.

Output Specification

The output should contain B - A + 1 lines. Each line should contain a single integer, the number of distinct prime factors of A, A+1, \ldots, B.

Sample Input

20
30

Sample Output

2
2
2
1
2
1
2
1
2
1
3

Comments

There are no comments at the moment.