Tìm tất cả các ước của n chia hết cho 2

đề bài: cho số nguyên dương n.tìm tất cả các ước của nó chia hết cho 2
ý tưởng của em rất bình thường là nếu số lẻ thì loại. còn số chẵn thì cho 1 vòng for (int i=2;i<=n/2;i=i+2) rồi để n%i==0.
mọi người có cách nào khác không ạ? cách của em check thì bị quá thời gian mất rồi

Căn n nhé :slight_smile: bài này chuyển thành: n = 2^k * m (m lẻ), chia thử m (căn), nhân với 2^1, …, 2^k.

4 Likes

anh có thể nói rõ hơn không ạ?em chưa hiểu lắm

Tức là như thế này:
Nếu n là số chẵn thì bạn có thể chuyển nó thành dạng n = 2^k * m (m là số lẻ).
Lúc này bạn đã biết được k số thỏa mãn yêu cầu đề bài là từ 2^1 đến 2^k.
Tiếp tục duyệt từ 3 đến sqrt(m) để tìm các ước của m. Các ước này nhân với từng cái ước 2^k hồi nãy sẽ ra thêm những số thỏa mãn đề bài.

7 Likes

nhưng bạn ơi ví dụ n=100 thì 100=2^1 * 50. 50 đâu phải số lẻ

100 = 2^2 * 25 nha, k phải là số lớn nhất.

4 Likes

à ok cám ơn bạn nhé <3

với 100 thì có 6 số
nhưng mình thử cách của b thì chỉ in ra có 4 số thôi
tại sao nhỉ ?
mong b rep:3

100 = 2^2 * 25
Từ 25 tìm ra 1, 5, 25 nữa.

2 Likes

Hi, lâu quá mới vào lại trang nên giờ mới trả lời bạn được.

Lí do ra mà bạn ra kết quả là 4 một phần cũng do mình viết chưa rõ đoạn tìm các ước của m ấy, mình đã bỏ qua hai ước mà mặc định các số nguyên (lớn hơn 2) đều có là 1m (chính nó) :crazy_face: . Vậy thì các bước làm sẽ như sau:

100 = 2^2 * 25
Các ước của 25 bao gồm 1, 525, vậy ta sẽ có 6 số:

  • 2^1 * 1 = 2
  • 2^2 * 1 = 4
  • 2^1 * 5 = 10
  • 2^2 * 5 = 20
  • 2^1 * 25 = 50
  • 2^2 * 25 = 100
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?