Biến dem=0 nằm trong đoạn code xuất các số nguyên tố từ 2 đến n có tác dụng gì?

c++

(Hoàng Thiên) #1
#include <iostream>

using namespace std;

int main()
{
    int n,i,j,dem=0;
    cin>>n;
    for(i=2;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            if(i%j==0)
                dem++;
        }
        if(dem==2) cout<<i<<" ";
        dem=0;
    }
   return 0;
}

Source code trên là để xuất các số nguyên tố từ 2 đến n. Em thắc mắc là không biết cái biến dem=0 nằm phía dưới có tác dụng gì v ạ !?


(SITUVN.gcd) #2

Mục đích của biến dem là đếm số lần chia hết cho 1 và chính số đó. Nếu 1 số chỉ chia hết cho 1 và chính nó (đúng 2 lần) thì đó là số nguyên tố.
Sau mỗi lần kiểm tra thì đặt biến dem về 0 để đếm lại cho số mới.

Tối ưu mã:

  • Bất kì số nào cũng chia hết cho 1. Chạy từ 1 là dư thừa. Vì nó là hiển nhiên. Nên lặp từ 2.
  • Nên chạy từ 2 đến sqrt (căn bậc 2) của số đó. Vì từ sqrt của số đó đến chính nó sẽ chắc chắc có 1 kết quả chia hết hiển nhiên cho chính nó.

Tóm lại: lặp từ 2 đến sqrt, nếu số đó chia hết cho bất kì số nào trong khoảng này thì đó không phải số nguyên tố.


(‏) #3

dem là số lượng ước số của i. Nếu số lượng ước số của i là 2 (1 và chính nó) thì nó là số nguyên tố.

đề nghị tử hình ai đặt tên hiểm hóc như thế này. Sao ko đặt là iDivisorsCount hay soLuongUocSoCuaI hay so_uoc_so_cua_i hay num_divisors_of_i v.v… Em sau này có viết code thì nhớ để tên mình vào, nếu có địa chỉ càng tốt để người đọc còn biết mà tìm đến nhà mà chém…


(rogp10) #4

Bài này chạy sàng :smiley:


(Hoàng Thiên) #5

em cảm ơn nhiều ạ :kissing_heart:


(Hoàng Thiên) #6

hihi cũng tại em mới học, lần sau em sẽ rút kinh nghiệm


(Hoàng Thiên) #7

e hiểu r ạ, cảm ơn bạn nhiều nha


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