Bi-primes discussion


#1

Did a little refactoring and logic adjustment. A little less seat of the pants in this one…

def is_prime(x):
  if x < 2: return False
  if x > 2:
    u = int(x ** 0.5) + 1
    n = 2
    while n < u:
      if x % n: 
        n += 1 if n == 2 else 2
        continue
      return False
  return True

def prime_factors(x):
  if is_prime(x): return "{} is Prime".format(x)
  factors = []
  u = int(x ** 0.5) + 1
  n = 2
  while n < u:
    y = x
    if is_prime(n):
      while y % n == 0:
        factors.append(n)
        y //= n
      if y != x and is_prime(y): factors.append(y)
    n += 1 if n == 2 else 2
  return factors

def semiPrimeDetector(x):
  return len(prime_factors(x)) == 2
print (3, prime_factors(3))
print (3, semiPrimeDetector(3))
print (69, prime_factors(69))
print (69, semiPrimeDetector(69))
print (89, prime_factors(89))
print (89, semiPrimeDetector(89))
Python 3.6.1 (default, Dec 2015, 13:05:11)
[GCC 4.8.2] on linux
 > 
 3 3 is Prime
 3 False
 69 [3, 23]
 69 True
 89 89 is Prime
 89 False
 >

https://repl.it/M4IF/4

Of course it is not ideal but it gives us a chance to view the ideal through this lens. What of it is fuzzy logic and where might there be need of recursion? Making this general construct more efficient is the next goal, but I suspect we will see improvements upon the themes in upcoming submissions.


[Challenge] Semi-Prime Numbers
#2

Moving on, rather than increment n and test for primeness in the prime_factors function, I’ve created a next_prime function to help with loading n up with a prime on every pass. Now I think the code is ready for the next level of the challenge.

def is_prime(x):
  if x < 2: return False
  if x > 2:
    u = int(x ** 0.5) + 1
    n = 2
    while n < u:
      if x % n: 
        n += 1 if n == 2 else 2
        continue
      return False
  return True

def next_prime(x):
  if x == 2: return 3
  n = x if x % 2 else x - 1
  while True:
    n += 2
    if is_prime(n): return n
def prime_factors(x):
  if is_prime(x): return "{} is Prime".format(x)
  factors = []
  u = int(x ** 0.5) + 1
  n = 2
  while n < u:
    y = x
    while y % n == 0:
      factors.append(n)
      y //= n
    if y != x and is_prime(y): factors.append(y)
    n = next_prime(n)
  return factors

def semiPrimeDetector(x):
  return len(prime_factors(x)) == 2

https://repl.it/M4IF/5

The program is pretty much self-explanatory at this point. The next trick will be to come up with a sequence generator to help with the count. Since I kind of suck at generators, any advice at this point would be welcome and appreciated.


#3

The above is flawed in that it detects false positives. Under 100, it returns True for 42, 66, and 78. The pair they all have in common is [2, 3] when they should be triplets,
[2, 3, 7], [2, 3, 11], and, [2, 3, 13], respectively. Still on the drawing board.

https://repl.it/M4IF/6

In the meantime, to get away from my own confirmation bias I decided to segue to a working solution that doesn’t try to do too much.

''' adapted from,
    http://www.sanfoundry.com/python-program-compute-prime-factors-integer/
    This adaptation returns only the distinct factors. Biprimes and perfect 
    squares are tested for by the caller.
    '''

def prime_factors(n):
  factors = []
  i = 1
  while i <= n:
    k = 0
    if n % i == 0:
      j = 1
      while j <= i:
        if i % j == 0:
          k += 1
        j += 1
      if k == 2:
        factors.append(i)
    i += 1
  return factors

end = ''' end adapted code '''
def semiPrimeDetector(x):
  n = prime_factors(x)
  return (len(n) > 1 and n[0] * n[1] == x) or n[0] ** 2 == x

def semiPrimeCount(x):
  count = 0
  for i in range(4, x + 1):
    if semiPrimeDetector(i):
      count += 1
  return count

https://repl.it/M87b

This one gives correct counts for both 30 and 100. It uses a cheat approach that arbitrarily truncates the left two items in the return list to test for biprimeness, or it tests for perfect squares.