Tăng tốc độ chạy của code

[tuanjggaa (Tuấn)]

Em làm bài này mà nó chạy lâu quá. Như lúc nhập 100000. Anh/chị có thể giúp em làm sao cho chạy nhanh hơn không (tối ưu).

Đề:

Nhập 1 số n bất kì. In ra trước nó có bao nhiêu số nguyên tố.

Ví dụ:
Input: 10; Output: 3
Input: 100000; Ouput: 9592

Bài làm:

    #include <iostream>
    #include <math.h>
    using namespace std;
    int main()
    {
    	int n, i, j;
    	cin >> n;
    	int dem = 0;
    	for (i = 2; i < n; i++)
    	{
    		bool prime = true;

    		for (j = 2; j < i; j++)
    		{
    			if (i % j == 0)
    			{
    				prime = false;
    				break;
    			}
    		}
    		if (prime == true)
    		dem++;
    		
    	}
    	cout << dem;
    }

[rogp10]

Dùng sàng đi bạn

Muh câu này người ta hỏi nhiều lắm rồi

[tuanjggaa (Tuấn)]

Em moi hoc dc 2 tuan @@ ko biet nhieu la sao anh giai thich them dc ko a.

[hungaya (Hung)]

Mới học 2 tuần vậy được rồi.
Nếu mình đưa ra bài toán này thì chỉ yêu cầu biết sử dụng vòng lặp và lồng câu lệnh điều kiện trong vòng lặp. Yếu tố nhanh hay chậm thì không care đâu. Và tést cũng không bao giờ test số lớn cả.

[rogp10]

Chưa hay 100k không vẹo nhưng 1b chạy ko kịp.

Em moi hoc dc 2 tuan @@ ko biet nhieu la sao anh giai thich them dc ko a.

Hình dung một bảng số từ 2 đến N. Nếu p là số nguyên tố thì 2p, 3p, … không phải là số nguyên tố nên gạch bỏ. Cuối cùng số nào không gạch thì số đó nguyên tố.

Thực ra chỉ cần gạch p^2, p^2+p, p^2+2p, …

[rogp10]

Chia thử nó lâu cực kì với lại người ta kêu đếm tức là không cần lưu gì cả.

[tuanjggaa (Tuấn)]

The co cach nao toi uu no ko nhi ? Neu co cho em xin Code voi a. Do Nop bai tren web truong. no tinh thoi gian chay tren day luon a.

[Phong_Ky_Vo (Tao Không Ngu.)]

Sorry mọi người kiến thức của mình còn ít.
Rất xin lỗi.