Gibt es ein Python-Programm, das Semi-Primes löst?

Question

so habe ich eine Formel, die Semi-Primes schneller löst als jedes Paar Primzahlen immer und immer wieder zu multiplizieren! Anstatt also lange raten und prüfen zu müssen (siehe unten), verwenden Sie die Grundteilung.

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

und dies ist mein Weg

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

es nicht die Länge hier viel ändern, aber es tut in größeren halb-Primzahlen. aber jetzt frage ich mich, ob es ein Python-Programm gibt, das das für mich tun kann? Bisher kann ich keins machen, aber ich arbeite daran.

Answer 1

, was Sie wollen, ist die Zahl faktorisiert, hier ist ein Beispiel dafür, wie

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: ")) 

der lustige Teil ist hier die prime_generator kann es so einfach sein wie nur die Zahlen Filterung mit einer is_prime Funktion wie zum Beispiel filter(is_prime,xrange(2,n+1)), oder etwas mehr wie das

EDIT Sieve of Eratostenes spezialisiert

die oben genannten, die einen allgemeinen Ansatz für das Problem verwenden, können durch die Prüfung weiter verbessert werden, als Semi-Primzahl nur genau zwei Faktoren haben, dann müssen wir nur die erste finden, entfernen Sie es von der Zahl und wenn was übrig bleibt ist Prime wir finde es. nur Dafür brauchen wir eine erstklassige Prüffunktion und einen Generator von Primzahlen

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: ")) 

Ich denke, dieser Algorithmus ist, dass Sie zu erklären versuchen, wie Sie für die zweite Primzahl zu suchen brauchen nicht sehen können (p2) der erste (p1) und der andere wird natürlich erscheinen, wenn es existiert.

Ich lasse die beiden Funktionen als Übung.

Für is_prime können Sie die einfache Probedivision verwenden, wie Sie in Ihrer Antwort zu tun, die durch die Art und Weise 2 als Haupt identifizieren scheitern, oder ein leistungsfähigeres test wie die Miller-Rabin test (Deterministic variants) (Sie können eine funktionierende Version finden in http://rosettacode.org) oder Baillie-PSW test.

Für die prime_generator können Sie, wie ich vor dem Sieb von Eratostenes erwähnt habe, oder einen unendlichen Prim-Generator verwenden. Sie können zum Beispiel in dieser Frage finden: Sieve of eratosthenes finding primes python und how to implement an efficient infinite generator of prime numbers in python. Letzteres ist mein Favorit

Answer 2

NIEMALS, ich habe es verstanden.

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]