bài tập vòng lặp trong lập trình C

#1

mọi người gúp e bài này
nhập số nguyên n và tính tổng các số nguyên tố nhỏ hơn n

#2

Bạn có ý tưởng gì chưa, có code thì đưa lên luôn, sai cho nào mọi người sửa giúp :blush:
Bài này cẩn thận không cần vòng lặp ấy chứ

#3 
 for (i=1;i<=n;i++)
       if (n%i==0)
           j++;
  if (j==2)          //kiem tra co phai la so nguyen to

mình chỉ có ý tưởng kiểm tra xem nó có phải là số ngto k và chưa suy nghĩ ra cách tìm các số ngto nằm trong khoảng nhỏ hơn n để tính tổng

#4

À mình nhầm cứ tưởng tính các số nguyên không thôi :blush:
Chạy biến j từ 1 đến n, kiểm tra biến đó có phải là nguyên tố không, nếu có thì cộng vào biến tổng :blush:
Bạn tham khảo topic này nhá.

#5

thực sự mình chưa học tới mảng bạn ơi, mà dùng điều kiện j để kiểm tra biến đó có phải là số ngto k bạn

#6

Thế bạn xem ở đây nhá :blush:

#7

Em nghĩ nên cải tiến thế này:

  • Mới đầu cho biến sum = 2 (2 là số nguyên tố).
  • Cho
for(int i = 3; i < n; i += 2){
     if(Check(i) == true) // Nếu số đó là SNT, bạn tự làm phần kiểm tra nhé
          sum += i; // Cộng vào tổng
}

Thế là xong. Thuật toán trên thật ra là thuật toán liệt kê các số nguyên tố < n, mình lợi dụng việc đó để cộng tổng luôn.
Giải thích: vì ngoài 2 ra, các số nguyên tố còn lại đều là số lẻ, nên ta để sum bắt đầu từ 2. Rồi để vòng lặp chạy từ 3, mỗi lần lặp thì tăng i thêm 2 thì nó sẽ luôn là số lẻ.

1 Like
#8

Cũng hay đấy :smiley:, mà em xem cái link trên chưa, họ có một số cải tiến nữa đấy :blush:

Tuy nhiên, suy nghĩ thêm một chút chúng ta sẽ thấy rằng không cần phải kiểm tra đến giá trị i = n – 1 mà thực chất chỉ cần tới n/2 (n div 2) vì không có ước số nào của n lớn hơn n/2.
Lại suy nghĩ thêm một chút chúng ta sẽ thấy rằng cũng không cần thiết phải kiểm tra đến giá trị n/2 mà chỉ cần đến căn bậc 2 của n là được (các bạn hãy tính toán một chút để thấy tại sao lại như vậy?)

#9

Dạ, cái chạy tới sqrt(n) là trong phần Check đó anh. :smiley:
Còn cộng tổng thì phải chạy đến khi nào >= n thì thôi (đề kêu v)

1 Like
#10

Hợp lý :blush: cách làm của em rất giống phương pháp Sieve of Eratosthenes (giống đoạn đầu )
http://www.caulacbovb.com/forum/viewtopic.php?f=12&t=12572

1 Like
#11

A, em nhớ rồi, cái đó là thuật sàn Eratosthenes, để liệt kê số nguyên tố :smiley:

1 Like
#12

Ukm, bây giờ người ta dùng thuật toán Miller - Rabin tìm nhanh hơn nhiều nữa nhưng mà anh đọc không hiểu :smile:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?