Erhalten Sie alle Faktoren einer Zahl (Iteratoren Showdown :)

Question

Sie sind alle Primfaktoren einer Zahl, zusammen mit ihren Multiplizitäten (höchste Mächte) gegeben.
Die Anforderung besteht darin, alle Faktoren dieser Nummer zu erzeugen.

Lassen Sie mich ein Beispiel geben:

Primfaktoren:

• 2 (Leistung: 3)
• 3 (Leistung: 1)

(was bedeutet, die Zahl ist 2^3 * 3^1 = 24)

Das erwartete Ergebnis ist:
1, 2, 3, 4, 6, 8, 12, 24

Ich denke darüber nach, dies (in C#) mit einigen verketteten benutzerdefinierten Iteratoren zu tun, einen für jeden Primfaktor, der von 0 bis zu zählen würde Macht dieser Primzahl.

Wie würden Sie das umsetzen? Verwenden Sie Ihre bevorzugte Sprache.

Dies bezieht dich auf problem #23 von Project Euler

Answer 1

Betrachten Sie alle möglichen Kombinationen von Leistungen. Erhöhen Sie für jede Kombination die Primzahlen auf ihre entsprechende Stärke und multiplizieren Sie das Ergebnis.

>>> from functools import reduce 
>>> from itertools import product, starmap 
>>> from operator import mul 
>>> 
>>> def factors(prime_factors): 
...  primes, powers = zip(*prime_factors) 
...  power_combos = product(*(range(p + 1) for p in powers)) 
...  prime_combos = (zip(primes, c) for c in power_combos) 
...  return (reduce(mul, starmap(pow, c)) for c in prime_combos) 
... 
>>> sorted(factors([(2, 3), (3, 1)])) 
[1, 2, 3, 4, 6, 8, 12, 24] 

Dieser Code verwendet Python 3.0. Neben dem Aufruf an sorted werden ausschließlich Iteratoren verwendet.

Nebenbemerkung: Schade, diese Frage scheint eher unpopulär zu sein. Ich möchte z.B. Einige funktionale Lösungen werden veröffentlicht. (Ich kann später versuchen, eine Haskell-Lösung zu schreiben.)

Answer 2

ich zum ersten Mal ohne eine IDE zur Hand schießen, so könnte es einige Fehler drin sein.

struct PrimePower 
{ 
    public PrimePower(Int32 prime, Int32 power) : this() 
    { 
     this.Prime = prime; 
     this.Power = power; 
    } 

    public Int32 Prime { get; private set; } 
    public Int32 Power { get; private set; } 
} 

Und dann nur diese rekursive Funktion.

public IEnumerable<Int32> GetFactors(IList<PrimePowers> primePowers, Int32 index) 
{ 
    if (index < primePowers.Length() - 1) 
    { 
     Int32 factor = 1; 
     for (Int32 p = 0; p <= primePowers[index].Power; p++) 
     { 
      yield return factor * GetFactors(primePowers, index + 1); 
      factor *= primePowers[index].Prime; 
     } 
    } 
    else if (index = primePowers.Length() - 1) 
    { 
     Int32 factor = 1; 
     for (Int32 p = 0; p <= primePowers[index].Power; p++) 
     { 
      yield return factor * GetFactors(primePowers, index + 1); 
      factor *= primePowers[index].Prime; 
     } 
    } 
    else 
    { 
     throw new ArgumentOutOfRangeException("index"); 
    } 
} 

Es könnte auch eine Erweiterungsmethode sein und IList<PrimerPower> könnte geschwächt wahrscheinlich IEnumerable<PrimePower> mit einigen Skip() und Take() Anrufe. Ich mag es auch nicht, den Index herumzugeben, aber die Alternative wäre das Kopieren der Prime-Power-Liste für jeden Anruf. In der Konsequenz denke ich, dass eine iterative Lösung vorzuziehen ist - ich werde eine hinzufügen, wenn ich wieder eine IDE habe.

Answer 3

Haskell.

cartesianWith f xs = concatMap $ \y -> map (`f` y) xs 
factorsOfPrimeFactorization = 
    foldl (cartesianWith (*)) [1] . map (\(p, e) -> map (p^) [0..e]) 

 
> factorsOfPrimeFactorization [(2, 3), (3, 1)] 
[1,2,4,8,3,6,12,24] 

das Ergebnis zu sortieren,

import Data.List 
cartesianWith f xs = concatMap $ \y -> map (`f` y) xs 
factorsOfPrimeFactorization = 
    sort . foldl (cartesianWith (*)) [1] . map (\(p, e) -> map (p^) [0..e]) 

---

Perl.

sub factors { 
    my %factorization = @_; 
    my @results = (1); 
    while (my ($p, $e) = each %factorization) { 
     @results = map {my $i = $_; map $i*$_, @results} map $p**$_, 0..$e; 
    } 
    sort {$a <=> $b} @results; 
} 

print join($,, factors(2, 3, 3, 1)), $/; # => 1 2 3 4 6 8 12 24 

---

J.

 
    /:~~.,*/"1/{:@({.^i.@{:@>:)"1 ] 2 3 ,: 3 1 
1 2 3 4 6 8 12 24 

---

Diese alle den gleichen Algorithmus implementieren, welche die Liste zu erzeugen, ist p , p , & hellip ;, p^e für jede Paar (p, und) in der Faktorisierung, und nehmen Sie das Produkt von Jede Menge wird über alle diese Listen in das kartesische Produkt eingefügt.

Answer 4

Wenn Sie kümmern sich nicht um die einzelnen Teilern, sondern um die Summe aller Teiler von n Sie vielleicht einen Blick auf die Divisor Function haben wollen:

Damit die Summe der Teiler von

ist

Answer 5

Sehr einfach zu tun. In der Tat habe ich einen Artikel in meinem Blog über diese Sache geschrieben. Schau dir diesen Code an.

#Application lists all factors/divisors for a number. 
targetNumber=input('What number do you want the factors for?\n> ') 
factors=[] 
for i in range(1,targetNumber): 
    if targetNumber%i==0: 
     factors.append(i) 
    elif targetNumber/i==1: 
     factors.append(targetNumber) 
     break 
print factors 

Read more