Ալգորիթմներ և Տվյալների Կառուցվածքներ

Պարզ արտադրիչների վերլուծելը

Յուրաքանչյուր դրական ամբողջ թիվ n ≥ 2 կարելի է ներկայացնել պարզ թվերի արտադրյալի տեսքով.

2=2=214=2⋅2=2249=7⋅7=7224=2⋅2⋅2⋅3=23⋅3175=3⋅5⋅5=31⋅5284=2⋅2⋅3⋅7=22⋅31⋅71\begin{aligned} 2 &= 2 &&= 2^1 \\ 4 &= 2 \cdot 2 &&= 2^2 \\ 49 &= 7 \cdot 7 &&= 7^2 \\ 24 &= 2 \cdot 2 \cdot 2 \cdot 3 &&= 2^3 \cdot 3^1 \\ 75 &= 3 \cdot 5 \cdot 5 &&= 3^1 \cdot 5^2 \\ 84 &= 2 \cdot 2 \cdot 3 \cdot 7 &&= 2^2 \cdot 3^1 \cdot 7^1 \end{aligned}

Թվերի հետ տարբեր գործողություններ (օրինակ, բաժանարարների քանակի հաշվումը, երկու թվերի ամենամեծ ընդհանուր բաժանարարի (GCD) կամ ամենափոքր ընդհանուր բազմապատկի (LCM) վերաբերյալ գտնելը և այլն) հաճախ հնարավոր է հեշտ անել, եթե ունենք տվյալ թվի պարզ արտադրիչների վերլուծությունը։

n թվի (օրինակ՝ 300) պարզ արտադրիչների վերլուծությունը ստանալու համար կարելի է սկսել ամենափոքր պարզ թվից p (2) և, եթե n-ը բաժանելի է p-ի, ապա շարունակաբար բաժանել n-ը այդ p-ով, քանի դեռ դա հնարավոր է (300 / 2 = 150, 150 / 2 = 75)։

Այնուհետև մեծացնել p-ն մեկով (p = 3) և նույն կերպ ստուգել բաժանումը (75 / 3 = 25)։

p-ն մեկով մեծացնելիս ստանում ենք p = 4։ Այս դեպքում չենք կարող n-ը բաժանել p-ի քանի որ n-ն արդեն բաժանել ենք որքան հնարավոր էր 2-ի նախորդ քայլերից մեկում, որը 4-ի բաժանարար է։ Այդ պատճառով n-ի արժեքը 4, 6, 8 և 2-ի ցանկացած բազմապատիկով չենք կարող նորից բաժանել։ Քանի որ աշխատանքի ընթացքում շարժվում ենք փոքրագույն p-ից ավելի մեծ թվերի ուղղությամբ, եթե որևէ փուլում արդեն հայտնաբերել ենք ինչ-որ պարզ բաժանարար, ապա դրա բազմապատիկներն այլևս չեն գործելու։

Հաջորդ քայլում 5-ի բաժանելիությունը ստուգելիս (75 / 5 = 5, ապա 5 / 5 = 1) շարունակում ենք նույն տրամաբանությամբ։ Գործողությունը դադարեցնում ենք այն պահին, երբ p-ն գերազանցում է n\sqrt{n} արժեքը։ Եթե հասնում ենք մի պահի, երբ p>np > \sqrt{n}, ապա մնացած n-ը ինքնին պարզ թիվ է, և այն կարելի է անմիջապես ավելացնել պարզ արտադրիչների ցուցակին։

Այդպիսով, մեր օրինակում 300-ը կարելի է ներկայացնել որպես 2⋅2⋅3⋅5⋅52 \cdot 2 \cdot 3 \cdot 5 \cdot 5։

n = ...                              # n-ը պետք է վերլուծել պարզ արտադրիչների
p, divisors, powers = 1, [], []      # p-ն՝ բաժանարար, divisors-ը՝ պարզ արտադրիչներն են, powers-ը՝ դրանց աստիճանները

while p * p <= n:                    # քանի դեռ p <= sqrt(n)
    p += 1                           # ամեն քայլին p-ն մեծացնում ենք 1-ով
    if n % p != 0:                   # եթե n-ը չի բաժանվում p-ի, անցնում ենք առաջ
        continue
    
    divisors.append(p)               # n % p == 0 => p-ն պարզ բաժանարար է
    powers.append(0)                 # դրա աստիճանը ամենասկզբում 0 է
    while n % p == 0:                # որքան հնարավոր է բաժանում ենք n-ը p-ով
        n //= p
        powers[-1] += 1              # ամեն բաժանումից հետո ավելացնում ենք համապատասխան աստիճանը

if n > 1:                            # եթե p > sqrt(n), ուրեմն n-ը պարզ թիվ
    divisors.append(n)               # ավելացնում ենք n-ը որպես բաժանարար
    powers.append(1)                 # նրա աստիճանը 1 է

print(list(zip(divisors, powers)))   # տպում ենք բաժանարարները և դրանց աստիճանները

Ալգորիթմի յուրաքանչյուր քայլի ընթացքում, եթե տրված բաժանարարով կարելի է բաժանել մեր թիվը, ապա բաժանում ենք և միաժամանակ ավելացնում ենք այդ բաժանարարի աստիճանը:

Մի քանի օրինակ դիտարկենք.

n = 24

  1. p = 2, n = 24 (առաջին քայլին p-ն 1-ից դարձավ 2)
    n % 2 == 0 ⇒ divisors = [2], powers = [0]
    n //= 2 ⇒ n = 12, powers = [1]
    n //= 2 ⇒ n = 6, powers = [2]
    n //= 2 ⇒ n = 3, powers = [3]

  2. p = 3, n = 3 ⇒ կանգ ենք առնում, քանի որ p * p = 9, որը մեծ է 2-ից

  3. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]

n = 75

  1. p = 2, n = 75

  2. p = 3, n = 75
    n % 3 == 0 ⇒ divisors = [3], powers = [0]
    n //= 3 ⇒ n = 25, powers = [1]

  3. p = 4, n = 25

  4. p = 5, n = 25
    n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0]
    n //= 5 ⇒ n = 5, powers = [1, 1]
    n //= 5 ⇒ n = 1, powers = [1, 2]

  5. p * p > n ⇒ կանգ ենք առնում ⇒ divisors = [3, 5], powers = [1, 2]

n = 84

  1. p = 2, n = 84
    n % 2 == 0 ⇒ divisors = [2], powers = [0]
    n //= 2 ⇒ n = 42, powers = [1]
    n //= 2 ⇒ n = 21, powers = [2]

  2. p = 3, n = 21
    n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0]
    n //= 3 ⇒ n = 7, powers = [2, 1]

  3. p * p > n ⇒ կանգ ենք առնում

  4. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]

n = 31

  1. p = 2, n = 31

  2. p = 3, n = 31

  3. p = 4, n = 31

  4. p = 5, n = 31

  5. p = 6, n = 31

  6. p * p > n ⇒ կանգ ենք առնում

  7. n > 1 ⇒ divisors = [31], powers = [1]

Առաջադրանք

Տրված է n ամբողջ թիվը. Անհրաժեշտ է գտնել n-ի ամենամեծ պարզ բաժանարարը։

Մուտք

Մուտքի միակ տողում տրված է մեկ ամբողջ թիվ n (2 ≤ n ≤ 10910^9):

Ելք

Ծրագիրը պետք է տպի n-ի ամենամեծ պարզ բաժանարարը։

Օրինակներ

Մուտք

Ելք

8

2

24

3

75

5

31

31

Բոնուս․ Ինչու՞ չենք ստուգում միայն պարզ թվերը։

Մեր ալգորիթմը բոլոր թվերը անցնում է հերթով 2, 3, 4, … մինչև n\sqrt{n}։ Թվում է, թե կարելի էր պարզապես անցնել միայն պարզ թվերով մինչև n\sqrt{n}-ը, սակայն նախ պետք է գտնել այն բոլոր պարզ թվերը, որոնք չեն գերազանցում n\sqrt{n}-ը, իսկ դա սովորաբար պահանջում է մոտ O(n⋅log⁡log⁡n)\mathcal{O}(\sqrt{n} \cdot \log \log \sqrt{n}) գործողություն։ Այսինքն՝ պարզ թվերի գտնելը կարող է ավելի ժամանակատար լինել, քան ուղղակի 2-ից մինչև n\sqrt{n} հերթականությամբ ստուգելը:

Կարո՞ղ եք մտածել այնպիսի իրավիճակ, երբ նախօրոք պարզ թվերի ցուցակ կազմելն ու դրանցով ստուգելը, գուցե, ավելի արդյունավետ լինի:

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB