 # [Challenge] Semi-Prime Numbers

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`

### 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]`.

### Hard Difficulty

Write `semiPrimeDetector` and `semiPrimeCount` as efficiently as possible.

### 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:

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

2 Likes

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

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 = 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 
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 = 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

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();

Basic difficulty using JavaScript.
I assume that there’s simpler solution, but it works: