Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Problem A: Distinct Prime Factors

"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 ≤ AB ≤ 1000000), determine the number of distinct prime factors for each integer between A and B, inclusive.

Input Format

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

Output Format

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

Sample Input

20
30

Sample Output

2
2
2
1
2
1
2
1
2
1
3

All Submissions
Best Solutions


Point Value: 7
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 15, 2014
Authors: Alex, FatalEagle

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Could someone give me some tips on how to reduce my time?

Might be a good idea to look at some other comments.


you sould generate the primes with the sieve of Eratosthenes, then loop again for it's prime factors

you should look up the definition of a prime number and prime factors