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

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

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

Թվերի հետ տարբեր գործողություններ (օրինակ, բաժանարարների քանակի հաշվումը, երկու թվերի ամենամեծ ընդհանուր բաժանարարի (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-ը ինքնին պարզ թիվ է, և այն կարելի է անմիջապես ավելացնել պարզ արտադրիչների ցուցակին։

Այդպիսով, մեր օրինակում 300-ը կարելի է ներկայացնել որպես ։

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

Ելք

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

Օրինակներ

Մուտք

Ելք

8

2

24

3

75

5

31

31

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

Մեր ալգորիթմը բոլոր թվերը անցնում է հերթով 2, 3, 4, … մինչև ։ Թվում է, թե կարելի էր պարզապես անցնել միայն պարզ թվերով մինչև -ը, սակայն նախ պետք է գտնել այն բոլոր պարզ թվերը, որոնք չեն գերազանցում -ը, իսկ դա սովորաբար պահանջում է մոտ գործողություն։ Այսինքն՝ պարզ թվերի գտնելը կարող է ավելի ժամանակատար լինել, քան ուղղակի 2-ից մինչև հերթականությամբ ստուգելը:

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

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue