# Prime numbers

• 05-03-2008, 03:54 PM
tercius
Prime numbers
Hello, I am trying to solve this problem:
A positive integer is said to be k-smooth if none of its prime factors exceeds k. Compute how many positive integers less than or equal to N are k-smooth.
Input

The input contains multiple test cases (less than 50). Each test case consists of two lines. The first one contains an integer N (1 ≤ N ≤ 5,000,000), the second one an integer k (1 ≤ k ≤ 1000).
Output

For each test case output a single line with the corresponding answer.

Can anyone help me? thanks
• 05-03-2008, 04:04 PM
Zosden
whats your problem. Nobody is going to do your assignment for you.
• 05-03-2008, 06:32 PM
sukatoa
Quote:

Nobody is going to do your assignment for you.
Maybe that is he's problem....

What have you done so far?
• 05-04-2008, 06:05 AM
hardwired
Line of sequential thinking leading to success in this:
1 generate some primes to be sure you can do so
2 for a given integer N find the primes that are factors of N
3 for a given limit k see if any of the primeFactors exceed k
4 print result