Tối ưu bài nộp liệt kê các số nguyên tố nhỏ hơn hoặc bằng N (T bộ test case) trên spoj

[Hung_Phan4 (Hưng Phan)]

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

long long search(long long n){
	int dem = 0;
	if(n < 2) return 0;
	for(long long i = 1; i <= n; ++i){
		if(n % i == 0){
			dem++;
		}
	}
	if(dem == 2)
		return 1;
	return 0;
}

void test(long long n){
	for(long long i =1; i<=n; ++i){
			if(search(i) == 1){
				cout << i << " ";
			}
		}
}

int main(){
	int t;
	long long n;
	cin >> t;
	while(t--){
		cin >> n;
		test(n);
	}
	return 0;
}

Bác nào giải thích thuật toán cho e với :((( (thuạt toán kiểm tra số nguyên tố)

void ngto(long long n){
	bool a[n+1];
	memset(a, true , sizeof(a)); // gan toan bo mang a gia tri la true
	for(int i=2;i*i<=n;i++){
		if(a[i] == true){ // cac so ngto
			for(int j=i*i; j <= n ; j+=i){   // loai cac so khong phai ngto
				a[j]= false;
			}
		}	
	}
	for(int i=2;i<=n;i++)
	{
		if(a[i]==true) cout << i<<" ";
	}
	cout <<endl;
	}

[rogp10]

Code trên là thuật toán sàng Eratosthenes đại loại là ta bắt đầu từ 2, 2 nghiễm nhiên là nguyên tố, vậy ta không nhận 4, 6, 8, 10, … nữa. Tiếp theo là số 3 nhận rồi thì bỏ 6, 9, 12, 15…, cứ như vậy đến hết.

[Hung_Phan4 (Hưng Phan)]

tks bác nhé,e làm đc r