Uzyskaj wszystkie czynniki liczby (iteratory showdown :)

Question

Dostajesz wszystkie czynniki pierwsze liczby, wraz z ich wielokrotnościami (najwyższymi mocami).
Wymaga się przedstawienia wszystkich czynników o tej liczbie.

Podam przykład:

czynniki pierwsze:

• 2 (power: 3)
• 3 (moc: 1)

(co oznacza, że ​​liczba jest 2^3 * 3^1 = 24)

Spodziewany wynik to:
1, 2, 3, 4, 6, 8, 12, 24

Zastanawiam się nad zrobieniem tego (w języku C#) z kilkoma łańcuchowymi niestandardowymi iteratorami, po jednym dla każdego współczynnika podstawowego, który będzie liczony od 0 do moc tej liczby pierwszej.

Jak to wdrożyć? Użyj swojego preferowanego języka.

Wiąże się to z problem #23Project Euler

Answer 1

Rozważ wszystkie możliwe kombinacje mocy. Dla każdej kombinacji podnieś liczby pierwsze do odpowiedniej mocy i pomnóż wynik.

>>> 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] 

Ten kod wykorzystuje język Python 3.0. Oprócz połączenia z sorted, używa wyłącznie iteratorów.

Uwaga boczna: szkoda, że ​​to pytanie wydaje się raczej niepopularne. Chciałbym zobaczyć np. niektóre funkcjonalne rozwiązania są publikowane. (Mogę spróbować napisać później rozwiązanie Haskell.)

Answer 2

ja najpierw strzelać bez IDE pod ręką, więc nie mogą być pewne błędy tam.

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; } 
} 

A potem tylko ta funkcja rekursywna.

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"); 
    } 
} 

To może być również metodę rozszerzenia i IList<PrimerPower> mógłby prawdopodobnie osłabiony do IEnumerable<PrimePower> z kilkoma Skip() i Take() połączeń. Nie podoba mi się również przekazywanie indeksu, ale alternatywą byłoby kopiowanie listy mocy głównej dla każdego połączenia. W konsekwencji myślę, że preferowane byłoby rozwiązanie iteracyjne - dodam je, jeśli będę miał IDE ponownie.

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] 

Aby posortować wyniki,

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 

---

Wszystkie one realizować ten sam algorytm, który jest do utworzenia listy P , p , i hellip ;, P^e dla każdego parę (p, e) w rozkładzie, i weź produkt każdy zestaw w produkcie kartezjańskim na wszystkich tych listach.

Answer 4

Jeśli nie dbają o pojedynczych dzielników, ale o sumę wszystkich dzielników n warto rzucić okiem na Divisor Function:

ten sposób sumę dzielników

jest

Answer 5

bardzo proste do zrobienia. W rzeczywistości napisałem artykuł na moim blogu na ten temat. Sprawdź ten kod.

#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