Szukanie dzielników liczby

Question

Robiąc zadanie z challange olimpijskiego koła informatycznego, natknąłem się na zadanie: https://szkopul.edu.pl/problemset/problem/fof/site/?key=statement

Jest tam napisane, że można znaleźc dzielniki pierwsze liczby w czasie pierwiastek 4 stopnia z n. Tyko jak?

Ja narazie tylko umiem te w pierwiastek 2 stopnia ze poprostu sprawdzam do pierwiastka.

Comments

odwrotność pierwiastkowania? 75%

---

w sensie?

---

a jak funkcja w c++ służy do potęgowania?

---

w sensie pow(x,y), czy szybkie potegowanie?

---

75% - to pow jak więcej to musisz pokombinować.

edit 25%- szybkie potęgowanie

---

@pasjonat_algorytmiki,  gdzieś przeczytałem, że

Aby obliczyć pierwiastek m-tego stopnia, wystarczy podnieść n do potęgi 1/m

i wygląda, że działa  [ on-line ]

import math

in_ = [ [144,2], [1000000001,3], [4,1] ]
for n, m in in_:
    print(math.floor(math.pow(n, 1/m)))

 

---

Tak tak to zadanie zrobiłem, tylko chodzi mi o to jak znaleźć dzielniki pierwsze w O(sqrt4stopnia z n)

---

@VBService, 

Jeszcze apropo tego zadania, to ten pomysł wydaje się dobry, ale ta funkcja gubi zaokrąglenia bo sa zmiennoprzecinkowe i wchodzi jedynie na 50pkt. Na 100pkt wchodzi wyszukiwanie bianarne po wyniku. Korzystajac z tego ze jesli x^m < n, to wszystkie x-1, x-2 itd nie musimy sprawdzac, a jesli x^m > n, to nie sprawdzamy tez wszystkich wiekszych x. W O(t * log n), mozna jeszcze napisac szybkie potegowanie zeby te potegi liczyl w logu, ale to i tak nie potrzebne bo m <= 5.