[Challenge] Semi-Prime Numbers


#1

This is our first ever guest challenge, written by the amazing @star3lord with no help from myself or Dan. If you would like to have your own challenge published, please pm me. Enjoy!


Code Challenge #24: October 11, 2017


Basic Difficulty

Write a function, semiPrimeDetector, that tests if a number, n is a semi-prime number.

  • Function Name: semiPrimeDetector
  • Input: integer n
  • Output: boolean: true if n is a semi-prime number else false.
  • Example: semiPrimeDetector(194) => True
Find out more about basic challenges.

Intermediate difficulty

Write a function, semiPrimeCount, that will print total number of semi-prime numbers below a number, n.

  • Function Name: semiPrimeCount
  • Input: integer n
  • Output: An integer c, count of all the semi-prime numbers below n.
  • Example: semiPrimeCount(30) will output 10, which includes semi-prime numbers - [4, 6, 9, 10, 14, 15, 21, 22, 25, 26].
Find out more about intermediate challenges.

Hard Difficulty

Write semiPrimeDetector and semiPrimeCount as efficiently as possible.

Find out more about hard challenges and Big O

EXTRA

Write a function to check if the output of semiPrimeCount is odd or even.

  • Output: 0 if semiPrimeCount output an even number, 1 if the output is odd

  • Example: semiPrimeCount(30) will output 10, so this function should output 0

  • Try to solve this without using semiPrimeCount.


Reply to this thread with a link to your code on repl.it to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.


The fine print:

Click the links to find out more about:


#2

Not a submission, just something to seed the pot. It is buggy, but seems to work on the basic difficulty.

def prime_factors(x):
  if x < 4: return "No prime factors"
  factors = []
  for n in range(2, int(x ** 0.5) + 1):
    y = x
    while y % n == 0:
      factors.append(n)
      y //= n
    if y != x and y > 1: factors.append(y)
  return factors

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

https://repl.it/M4IF


#3

A post was split to a new topic: Bi-primes discussion


#4

Python 3.6 -

Basic / Intermediate / Hard Challenge :

Semi prime are product of two prime numbers. Thus, to test them, we only need to find its factors other than 1 and itself. Also, we only need to find first two factors(if there are) - if product of those two factors is the number itself then it is semi primes otherwise the number has another factor so it is not a semi prime number.

def semiPrimeDetector(n):
    factor = factorGenerator(n)
    try:
        return next(factor) * next(factor) == n
    except:
        return False

Here factorGenerator is a generator function of python which returns factors of a number one by one in ascending order. I have used a generator function here to save time and memory used in finding all the factors at once(which are not needed here).

factorGenerator
def factorGenerator(n):
    for prime in primeGenerator(int(n ** .5)+1):
        while n % prime is 0:
            yield prime
            n //= prime
    if n > 1:
        yield n

primeGenerator is also a generator function like factorGenerator which outputs prime numbers till an upper limit.

def primeGenerator(limit):
    if limit >= 2: yield 2
    if limit >= 3: yield 3
    else: return
    limit += 1
    correction = (limit % 6) > 1
    limit = [limit, limit-1, limit+4, limit+3, limit+2, limit+1][limit%6]
    sieve = [True] * (limit // 3)
    sieve[0] = False
    threshold = int(limit ** .5) // 3 + 1
    for i in range(threshold):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[            (k*k)//3        :: 2*k ] = [False] * ( (limit//6 - (k*k)//6 - 1)//k + 1 )
            sieve[ (k*k + 4*k - 2*k*(i%2))//3 :: 2*k ] = [False] * ( (limit//6 - (k*k + 4*k - 2*k*(i%2))//6 - 1)//k + 1 )
            yield k
    for i in range(threshold, limit//3 - correction):
        if sieve[i]:
            yield (3 * i + 1) | 1

Now the function to count semi prime numbers.
We don’t need to check if every number lower than the input number is semi prime or not and then count the semi prime numbers, we only need to find prime numbers lower than the input number, find products in combination of twos and count the number which are lower than the input number. Also, first prime number is 2 so we only need to find prime numbers lower than half of input number because any prime number greater than half of input number, if multiplied with any other prime number, will be greater or equal the input number.
Ex - for input 30, primes are 2, 3, 5, 7, 11 and 13, so possible semi primes are 2x2, 2x3, 2x5, 2x7, 2x11, 2x13, 3x3, 3x5, 3x7 and 5x5 thus total semi prime numbers smaller than 30 are 4, 6, 10, 14, 22, 26, 9, 15, 21 and 25

def semiPrimeCount(n):
    primes = primesSieve(n//2)
    end = len(primes)
    count = i = 0
    for prime in primes:
        j = i
        while j < end and prime*primes[j] < n:
            count += 1
            j += 1
        if j is i:
            return count
        i += 1
    
    return count

Here, semiPrimeCount uses primesSieve, a function which return a list of all prime numbers bounded an upper limit, to find prime numbers.

primesSieve
def primesSieve(limit):
    if limit < 2: return []
    elif limit < 3: return [2]
    limit += 1
    correction = (limit % 6) > 1
    limit = [limit, limit-1, limit+4, limit+3, limit+2, limit+1][limit%6]
    sieve = [True] * (limit // 3)
    sieve[0] = False
    for i in range(int(limit ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[            (k*k)//3        :: 2*k ] = [False] * ( (limit//6 - (k*k)//6 - 1)//k + 1 )
            sieve[ (k*k + 4*k - 2*k*(i%2))//3 :: 2*k ] = [False] * ( (limit//6 - (k*k + 4*k - 2*k*(i%2))//6 - 1)//k + 1 )
    return [2, 3] + [ (3 * i + 1) | 1 for i in range(1, limit//3 - correction) if sieve[i] ]

https://repl.it/NAAy


#5

My submission for this is simple. You basically input your number (inside the code) and It prints either if the number is or is not semi-prime. [https://repl.it/N6wE/0]
To have The code put a number in the parenthesis of semiPrimeDetector();


#6

Basic difficulty using JavaScript.
I assume that there’s simpler solution, but it works:
https://repl.it/@Dunjamarc/SemiprimeNumberDetector
Description provided in the code comment.