Codeforces: A. Almost Prime

The problem is from codeforces: http://www.codeforces.com/problemset/problem/26/A

The input range is small which means even the worst brute-force methods can pass the test. The straightforward implementation is . Defining a check function which will return true if the number of prime divisors is exactly two i.e. almost prime. However, the implementation can be improved in the check function in a few small aspects. For example, skipping the natural number 1 to 5 because they are not ‘almost prime’. The prime numbers in the divisor extraction process can skip to odd numbers after 2, 3, for example, 5, 7, 9 … Another improvement is obvious: if the number of current prime divisor is larger than two, no further divisor extraction will be required, rather, the function returns false straight away.

The Python solution is presented, which solves the problem within 220 ms.

#!/usr/bin/env python
# https://helloacm.com
n = int(raw_input())

def chk(n):
    i = 2
    j = 0
    k = 1
    while n > 1:
        u = n % i == 0
        if u:
            while n > 1:
                n /= i # divisor extraction
                if n % i > 0:
                    break
        if i == 3:
            k = 2 # skip even numbers
        i += k
        if u:
            j += 1
            if j > 2: # can't be almost prime
                return False
    return j == 2
        
s = 0
for i in xrange(6, n + 1):
    if chk(i):
        s += 1

print s

–EOF (The Ultimate Computing & Technology Blog) —