Bài 38: Đếm số chính phương

Bài 38:
Cho N nguyên dương. Hãy đếm số lượng số chính phương nhỏ hơn hoặc bằng N
BAI38.INP BAI38.OUT
10 3
Thuật toán:
Cách 1: Độ phức tạp của thuật toán O(N) (N ≤ 106).
res = 0;
Duyệt (i, 1, N)
Nếu i là số chính phương thì
res++;
Cách 2: Độ phức tạp của thuật toán là O(1).
….
8: 1, 4
9: 1, 4, 9
10: 1, 4, 9
11: 1, 4, 9
12: 1, 4, 9
….
15: 1, 4, 9
16: 1, 4, 9, 16
17: 4 số
…
24: 4 số
25: 5 số
Gọi kết quả là Res. T a đã chứng minh được Res = trunc(sqrt(N));
cout << res;

Video bài giảng:

Code:

from math import sqrt
n = int(input())
cnt = 0
for i in range(1, n + 1):
    if sqrt(i) == int(sqrt(i)):
        cnt += 1
print(cnt)

Code:

from math import sqrt
n = int(input())
print(int(sqrt(n)))