This community-built FAQ covers the “Semi-Prime Numbers” code challenge in Python. You can find that challenge here, or pick any challenge you like from our list.
Top Discussions on the Python challenge Semi-Prime Numbers
There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
You can also find further discussion and get answers to your questions over in #get-help.
Agree with a comment or answer? Like () to up-vote the contribution!
def semi_prime_count(n):
count = 0
for i in range(4, n):
facts = numFactors(i)
for fact in facts:
if isPrime(fact[0]) and isPrime(fact[1]):
count += 1
return count
def numFactors(n):
newlst =
num = int(n**0.5)+1
for i in range(2, num):
if n % i == 0:
other = n // i
newlst.append((i, other))
return newlst
def isPrime(n):
if n == 1:
return False
if n == 2:
return True
num = int(n ** 0.5) + 1
for i in range(2, num):
if n % i == 0:
return False
return True
import numpy as np
import math
def semi_prime_count(n):
list_of_primes = [n for n in range(2, n + 1) if is_prime(n)]
list_of_semi_primes = []
for x in list_of_primes:
for y in list_of_primes:
if x * y < n and x * y not in list_of_semi_primes:
list_of_semi_primes.append(x*y)
return len(list_of_semi_primes)
def is_prime(n):
if n == 2:
return True
for i in range(2, math.ceil(np.sqrt(n)) + 1):
if n % i == 0:
return False
return True
semi_prime_count(10)
def semi_prime_count(n):
def isprime(i):
n= int(i/2)
while n>=2:
if i%n == 0 :
return False
n = n-1
return True
def is_product_two(number):
i = 2
count = []
while i<=number:
if number%i == 0 and isprime(i):
count.append(i)
number = int(number/i)
else:
i += 1
if len(count)==2 or (len(count)==1 and count[0]*count[0]==number):
print("True")
print(count)
return True
print("False")
print(count)
return False
count = 0
for i in range (1, n):
if is_product_two(i):
count +=1
return count
print(semi_prime_count(10))
def semi_prime_count(n):
count = 0
for i in range(n):
if compare_divisors(i):
count += 1
return count
#Checks if there is at least one pair of prime numbers that have n as the product
def compare_divisors(n):
primes = get_primes(n)
for i in primes:
if n / i in primes:
return True
return False
#Returns a list of prime numbers up to (but not including) n
def get_primes(n):
primes = list() #Variable i will be the possible prime number, while j is the iterating number that will check for every possible divisor between 2 and i
for i in range(1, n):
isPrime = True
for j in range(i):
if j > 1 and i % j == 0:
isPrime = False
if isPrime:
list.append(primes, i)
return primes
Got it down to 0.1 seconds to find the answer for 1000000 with no additional modules which is quite good. One can probably improve the Sieve with numpy and other techniques.
Also please highlight the non-inclusive in the question, since most of my time working on this challenge was spend figuring out why my solutions were wrong because of me not reading correctly.
def primes(n):
num = [i for i in range(1,n,2)]
for p in range(1,int(len(num)/2)):
if num[p] == 0:
continue
for q in range(p,len(num),2*p+1):
if q == p:
continue
num[q] = 0
num[0] = 2
return [num[i] for i in range(len(num)) if num[i] != 0]
def semi_prime_count(n):
n -= 1
if n < 4:
return 0
l = primes(int(n/2)+1)
counter = 0
for p in range(len(l)):
for q in range(p,len(l)):
if l[p] * l[q] > n:
break
counter += 1
return counter
print(semi_prime_count(1000000))
def is_prime(n): #first defining a function that identifies prime numbers (returns true/false)
if n == 1:
return False
else:
for i in range(2, n - 1):
if n % i == 0:
return False
return True
def semi_prime_count(n):
l = [] #first we need an empty list (len of l will be returned)
for i in range(1, n): #checking for every number between 1 and n
j = 1 #initializing index for while-loop (can be removed if done in for-loop)
while j < i: #checking every number between 1 and i
if is_prime(j) and is_prime(int(i/j)) and i/j == int(i/j): #i is a semi prime number if these conditions are met (notice that is_prime only accepts integers, so to avoid rounding mistakes we have to add the third condition)
l.append(i)
break
else:
j += 1 #no infinite while loops here!
return len(l) #the length of the list is the number of semi prime numbers we found in range(n)
print(semi_prime_count(100))
I might be able to optimize prime number finder better so it can search for larger n but… oh well
def prime_number(n):
# prime number list finder
if n < 2:
return []
# if n >= 2, 2 is a prime number for all numbers <= n)
listy = [2]
for i in range(3, n+1):
# for all numbers from 3 to n
for j in range(0, len(listy)):
# going through the list of primes (listy)
if i % listy[j] == 0:
# ignore if not prime
break
if j == len(listy)-1:
# if not divisible by all prime numbers in the list, it is a prime number and gets appended to listy.
listy.append(i)
return listy
def semi_prime_count(n):
primes = prime_number(n)
sp = []
answer = []
counter = 0
# ignores cases where there are less than 2 primes.
if len(primes) < 2:
return 0
# take the product of 2 prime numbers and append to sp
for i in range(0,len(primes)):
for j in range(0, len(primes)):
sp.append(primes[i]*primes[j])
# removing duplicates and sorting list by converting to dict, then to sorted list
sp = sorted(list(dict.fromkeys(sp)))
for k in sp:
# for all elements in sp
if k >= n:
# find the point which k >= n, ignore the rest. (answer is the answer)
break
answer.append(k)
# return len(answer)
return len(answer)
print(semi_prime_count(3000))
from itertools import product
def is_prime(n):
is_prime = True
if n == 0 or n == 1:
return False
if n == 2:
return True
for i in range(2, (n//2)+1):
if n % i == 0:
is_prime = False
break
return is_prime
def find_primes(n):
primes = list()
for num in range(n):
if is_prime(num):
primes.append(num)
return primes
def semi_prime_count(n):
primes = find_primes(n)
products = set(tuple(x) for x in list(map(sorted, product(primes, repeat=2))))
count = 0
for x in range(2, n):
for t in products:
if (t[0]*t[1]) == x:
count += 1
return count
print(semi_prime_count(10))
def is_prime(n):
return not any(n % x == 0 for x in range(2, n))
def factor_pairs(n):
return [(x, y) for x in range(1, n) for y in range(1, n) if x * y == n]
def semi_prime_count(n):
semi_primes = 0
for _ in range(1, n):
primes = []
if is_prime(_):
continue
for x, y in factor_pairs(_):
if x in primes or y in primes:
continue
if all([is_prime(x), is_prime(y)]):
semi_primes += 1
primes.append(x)
primes.append(y)
continue
return semi_primes
print(semi_prime_count(10))
def semi_prime_count(n):
primes =
for num in range(n):
if num > 1:
for i in range(2,num+1):
if num%i == 0:
primes.append(i)
break
primes = list(set(primes))
semi_prime =
for base in range(len(primes)-1):
num1 = primes[base]
for ind in range(base, len(primes)):
mult = num1 * primes[ind]
if mult < n:
semi_prime.append(mult)
I used the prime factorization algorithm for this.
I put checking whether a number is semi-prime as a separate function.
code
from math import sqrt, ceil, floor
def is_semi_prime(n):
if (n < 4):
return False
prime_factors = []
d = 2 # first possible prime divisor is 2
while n > 1 and d <= n:
if (n % d) == 0:
prime_factors.append(d) # if d is a factor, add it to the list
n = n // d # divide by d if d is a factor
else: # if d is not a factor, go to next possible divisor
d += 1
return len(prime_factors) == 2 # check if have 2 prime factors
def semi_prime_count(n):
count = 0
for x in range(1, n):
if (is_semi_prime(x)):
count += 1
return count
print(semi_prime_count(10))
def is_prime(n):
if n == 1:
return False
#added time efficiencies
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
for i in range(2,n):
if n % i == 0:
return False
return True
def semi_prime_count(n):
count = 0
seen = set()
for num in range(n):
for i in range(2,num):
if num not in seen and is_prime(i) and num % i == 0 and is_prime(num//i):
seen.add(num)
count += 1
return count
semi_prime_count(10)
def semi_prime_count(n):
primes = []
for i in range(2, n + 1):
counter = 0
for k in range(1, i + 1):
if i % k == 0:
counter += 1
if counter == 2:
primes.append(i)
new_list = [num for num in range(n+1)]
newer_list = [new_list[i] for i in range(2, len(new_list)-1) if new_list[i] not in primes]
counter1 = 0
for num in newer_list:
for i in range(len(primes)):
for k in range(i+1, len(primes)):
if num == primes[i]*primes[k]:
counter1 += 1
if num == primes[i]**2:
counter1 +=1
return counter1
print(semi_prime_count(11))
) below.
) to up-vote the contribution!