Chen prime finder

Question

I've written a programme to find Chen primes. A Chen prime p is a prime number where (p + 2) is either also a prime number or has two prime factors.

I've got it working to the best of my knowledge: the first few values are correct.

def isprime(n):
  for m in range(2, int(n**0.5)+1):
     if not n%m:
        return False
  return True
m = 2
while True:
    if isprime(m):
        b = (m + 2)
        if isprime(b):
            print(m)
        for i in range(2, int((b)**0.5)+1):
            if b%i == 0:
                if isprime(i):
                    j = b/i
                    if isprime(j):
                        print(m)
    m = m + 1

The isprime(n) function definitely works; it's the while loop I'm more concerned with.

Answer 1

The excessive nesting could be reduced with more Pythonic looping. Since you are using Python 2, xrange() would be more appropriate than range(). Also, any(generator expression) and itertools.count() would help reduce nesting. To promote code reuse, the results should be yielded instead of printed.

Here is a translation of your code, without changing the algorithm:

from itertools import count

def is_prime(n):
    """Test n for primality. Warning: invalid result for n <= 1."""
    return not any(n % f == 0 for f in xrange(2, int(n**.5) + 1))

def chen_primes():
    """Generate primes p where (p + 2) is either prime or a product of two
       primes."""
    for a, b in ((n, n + 2) for n in count(2)):
        if is_prime(a):
            if is_prime(b):
                yield a
            elif any(
                b % f == 0 and is_prime(f) and is_prime(b // f)
                for f in xrange(2, int(b**.5) + 1)
            ):
                yield a

for p in chen_primes():
    print p

@Caridorc has pointed out that your isprime() is technically incorrect, and you rightly observed that the bug makes no difference in this problem. Even so, it is an issue that deserves to be clearly documented in a docstring.

---

You could define a max_factor() helper to reduce code repetition. Note that with the proper logic, it is not necessary to test i for primality. I also suggest doing special-case handling to take care of even numbers.

from itertools import count

def largest_factor(n):
    if n > 2 and n % 2 == 0:
        return n // 2
    for f in xrange(3, int(n**.5) + 1, 2):
        if n % f == 0:
            return n // f
    return n

def is_prime(n):
    return 1 < largest_factor(n) == n

def chen_primes():
    yield 2
    for a, b in ((n, n + 2) for n in count(3, 2)):
        if is_prime(a):
            f = largest_factor(b)
            if f == b or is_prime(f):
                yield a

for p in chen_primes():
    print p

Answer 2

\$0\$ and \$1\$ corner cases

\$0\$ and \$1\$ are not primes, but your code returns:

>>> isprime(0), isprime(1)
(True, True)

is_chen_prime function and helper function

is_chen_prime should be a function of its own to improve re-usability.

A function to check if a number has two prime factors will make the code more similar to the mathematical description of the problem:

def is_chen_prime(n):
    return is_prime(n) and (is_prime(n + 2) or has_two_prime_factors(n + 2))