Есть ли программа Python, которая разрешает полупростые числа?

Question

поэтому у меня есть формула, которая решает полупростые числа быстрее, чем умножение каждой пары простых чисел снова и снова! поэтому вместо того, чтобы использовать длинную галочку и проверку (показано ниже), вы используете базовое деление.

semi prime = 15 ... 2 * 3, 2 * 5, 2 * 7, 3 * 5 ... primes 3 and 5 

и это мой путь

semi prime = 15 ... 2/15, 3/15 ... primes ... primes 3 and 5 

это не меняет длину много здесь, но это происходит в больших полуприцепов простых чисел. но теперь я задаюсь вопросом, есть ли программа python, которая может сделать это для меня? пока я не могу это сделать, но я работаю над этим.

Answer 1

что вы хотите, чтобы Факторизует номер, вот пример того, как

def prime_generator(n): 
    """produce all the prime numbers less or equal to n""" 
    #put here the code for this 

def prime_factorization(n): 
    """return a list of with the all prime factors of n including their multiplicity""" 
    result=[] 
    for p in prime_generator(n): 
     while n%p==0: #while p divide n... 
      result.append(p) 
      n = n//p 
     if n<=1: 
      break 
    return result 

def is_semi_prime(n): 
    factors = prime_factorization(n) 
    if len(factors) == 2: 
     print n, "is a semi prime with those prime factors:", factors 
    else: 
     print n, "is not a semi-prime" 

is_semi_prime(input("enter a number: ")) 

забавная часть здесь является prime_generator он может быть столь же просто, как только фильтрации номера с is_prime функции как, например, filter(is_prime,xrange(2,n+1)), или что-то более специализированы как Sieve of Eratostenes

EDIT

выше, который использует общий подход к проблеме, может быть дополнительно улучшен с помощью специализированной проверки, поскольку полупростое число имеет ровно два фактора, тогда нам нужно всего лишь найти первое, удалить его из числа, и если все остальное будет простым, Найди это. Для этого нам нужен главная функция проверки и генератор простых чисел

def is_prime(n): 
    #put here the code for this 


def prime_generator(n): 
    #put here the code for this 


def is_semi_prime(n): 
    p1,p2 = 0,0 
    for p1 in prime_generator(n): 
     if n%p1==0: 
      p2 = n//p1 
      break 
    if is_prime(p2): 
     print n, "is a semi prime with those prime factors:", p1, p2 
    else: 
     print n, "is not a semi-prime" 

is_semi_prime(input("enter a number: ")) 

Я думаю, что это алгоритм, который вы пытаетесь объяснить, как вы можете видеть, не нужно искать второй штрих (p2) только первый (p1), а другой, естественно, появится, если он существует.

Я оставляю две функции, необходимые в качестве упражнения.

Для is_prime вы можете использовать простое пробное разделение, как и вы в своем ответе, который, кстати не в состоянии определить 2 как штрих или более мощный test вроде Miller-Rabin test (Deterministic variants) (вы можете найти рабочую версию в http://rosettacode.org) или Baillie-PSW test.

Для prime_generator вы можете использовать, как я упоминаю перед сито Эратостенов, или использовать бесконечный первичный генератор. Вы можете найти, например, в этом вопросе: Sieve of eratosthenes finding primes python и how to implement an efficient infinite generator of prime numbers in python. Последний мой любимый

Answer 2

НИКОГДА НЕ УДОВЛЕТВОРЕН, Я ИЗОБРАЖАЛ.

import math 

running = True 

prime_1 = 0 
prime_2 = 0 
semi_prime = 0 

n = 0 

semi_prime = input('Enter Semi-Prime: ') 

while running: 

    if prime_1 * prime_2 == semi_prime: 

     print('your 2 primes are') 
     print([prime_1]) 
     print([prime_2]) 
     running = False 

    else: 

     n += 1 

     def is_prime(number): 
       if number < 2: 
        return False 
       if number % 2 == 0: 
        return False 
       else: 
        for i in range(3, number): 
          if not number % i: 
           return False 
        return True 



     #This array stores all the prime numbers found till n 
     primes = [] 

     for i in range(100000): 
       if is_prime(i): 
        primes.append(i) 
       if len(primes) == n: 
        break 

     print("next prime is " + str(primes[n-1])) 

     prime_1 = primes[n-1] 
     prime_2 = semi_prime/primes[n-1]