Có ai biết thuật toán dùng để xác định số chính phương ngắn gọn và hiệu quả không?
Hiện nay tui được đề nghị 3 thuật toán :
1. sqr(sqrt(n))=n
2. round(sqrt(n))=sqrt(n)
3. xác định trong lân cận [ [sqrt(n)]-1; [sqrt(n)]+1 ]: chỉ cần có một số nguyên trong lận cận đó bình phương lên bằng n thì n là số cp.
3 thuật toán trên đều đúng trong trường hợp n là số Cp. Thuật toán 1 bị sai vì gần như lúc nào cho ra KQ n là số Cp. 2 thuật toán còn lại cũng bị sai khi n quá lớn. Tui đã thử trong Pascal, FreePascal, Delphi 7, Delphi for .NET, VB.NET, PHP (thử tt 1,2,3); VC++.NET (thử tt 1 và 3) với các kiểu longint, int64, uint64, qword.
Có ai biết thuật toán nào khác ko?
Bookmarks