K-Sejun Numbers
InterviewTime limit2sMemory limit128 MB
Count integers from 1 to N whose every prime factor is at most K, given N up to 100000 and K up to 100.
- Level
Easy3 of 10
- Topics
- Math, Number theory, Brute force
- Solved
- No attempts yet
Problem
O Sejun calls a positive integer a K-Sejun number if every prime factor of that integer is at most K.
The number 1 has no prime factors, so it is counted as a K-Sejun number for every K.
Write a program that counts how many positive integers at most N are K-Sejun numbers.
Input
The first line contains a positive integer N.
The second line contains a positive integer K.
N is at most 100,000, and K is at most 100.
Output
Print the number of K-Sejun numbers among the positive integers at most N.