ตรวจสอบว่าจำนวนเต็มสามารถแสดงเป็นผลรวมของกึ่งไพรม์สองตัวใน Python . ได้หรือไม่

สมมติว่าเรามีตัวเลข n เราต้องตรวจสอบว่า n สามารถแสดงเป็นผลรวมของกึ่งไพรม์สองตัวได้หรือไม่

อย่างที่เราทราบกันดีว่าเซมิ-ไพรม์เป็นตัวเลขถ้าสามารถแสดงเป็นผลคูณของจำนวนเฉพาะสองจำนวนได้ ตัวเลขกึ่งไพรม์สองสามตัวแรกคือ (ช่วง 1 - 100):4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95.

ดังนั้น หากอินพุตมีค่าเท่ากับ n =108 เอาต์พุตจะเป็น True เนื่องจากเป็นผลรวมของ 14 และ 94 ทั้งคู่เป็นแบบกึ่งไพรม์

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• MAX :=10000 สมมติว่าอินพุตที่กำหนดเป็นผลรวมของกึ่งไพรม์ซึ่งอยู่ในช่วง 1 ถึง 10,000
• nums :=รายการใหม่
• s_prime_flags :=อาร์เรย์ขนาด MAX และเติมด้วย False
• กำหนดฟังก์ชัน get_semi_primes() นี่จะใช้เวลา
• สำหรับ i ในช่วง 2 ถึง MAX - 1 ทำ
  • นับ :=0
  • num :=i
  • j :=2
  • ในขณะที่นับ <2 และ j^2 <=num ให้ทำ
    • ในขณะที่ num หารด้วย j ลงตัว, do
      • น้ำ :=น้ำ / j
      • นับ :=นับ + 1
    • j :=j + 1
  • ถ้า num> 1 แล้ว
    • นับ :=นับ + 1
  • ถ้านับเท่ากับ 2 แล้ว
    • s_prime_flags[i] :=จริง
• ใส่ i ต่อท้ายตัวเลข
• จากวิธีหลัก ให้ทำดังนี้ -
• โทร get_semi_primes()
• ผม :=0
• ในขณะที่ nums[i] <=ผลหารของ (n / 2) ทำ
  • ถ้า s_prime_flags[n - nums[i]] เป็นจริง ดังนั้น
    • คืนค่า True
  • ผม :=ผม + 1
• คืนค่าเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

MAX = 10000
nums = []
s_prime_flags = [False] * MAX
def get_semi_primes():
   for i in range(2, MAX):
      count = 0
      num = i
      j = 2
      while count < 2 and j * j <= num:
         while num % j == 0:
            num /= j
            count += 1
      j += 1
      if num > 1:
         count += 1
      if count == 2:
         s_prime_flags[i] = True
         nums.append(i)
def solve(n):
   get_semi_primes()
   i = 0
   while nums[i] <= n // 2:
      if s_prime_flags[n - nums[i]] == True:
         return True
      i += 1
   return False
n = 108
print(solve(n))

อินพุต

[4, 2, 3], 11

ผลลัพธ์

True