Editorial for Različiti činioci

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: TadijaSebez

Ako postoji delilac $D$ ~D~ broja $N$ ~N~ tako da je $1<D<\sqrt{N}$ ~1<D<\sqrt{N}~ onda se $N$ ~N~ može predstaviti kao proizvod $D \times \frac{N}{D}$ ~D \times \frac{N}{D}~. Kako je $D<\sqrt{N}$ ~D<\sqrt{N}~ onda je $\frac{N}{D}>\sqrt{N}$ ~\frac{N}{D}>\sqrt{N}~ pa su $N$ ~N~ i $\frac{N}{D}$ ~\frac{N}{D}~ različiti te je odgovor "DA". U suprotnom $N$ ~N~ je prost broj ili kvadrat prostog broja i u tom slučaju je očigledno odgovor "NE".

Vremenska složenost: $O(T\sqrt{N})$ ~O(T\sqrt{N})~

Comments

There are no comments at the moment.