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.