Liệt kê các số nguyên tố từ N -> M

[08520001]

Mời các bạn giải bài của 1 em khóa 6 đưa rahttp://forum.uit.edu.vn/threads/2176...cac-cach-co-th do lot nu.

[09520019]

Ủa sao biết bé hơn 1s thế Châu :-? anh không hiểu, có cách tính nhẩm nào à chỉ anh với :-)

ko tính nhẩm a, e đọc tài liệu rồi nên đọc đc nó chứng minh độ phức tạp của Sieve of Eratosthenes, từ bài code của nó với code của anh thì em so ra bài a chạy lâu hơn 1 khoảng không đáng kể nên em nghĩ nó chạy khoảng 1s thôi.

Nhưng có nhiều cách khoác ngoài Sieve of Eratosthenes (và có khả năng nhanh hơn nếu code tốt ^^)
Ở đây anh Toàn có đoạn này:
for (int j = 2 ; j < maxRange ; j++){sieve[j*i] = false;.....
Cách tốt hơn mà em đọc đc là for (j = i * i;j <= max Range; j+=i)...... ở đây rất dễ hiểu: 2 * i đã đi qua rồi thì mình ko cần duyệt lại i * 2
for(int i = 2; i <=upperRange/2 ; i++){
Ở đây em chỉ cần i * i <= upperRange thôi, lại nhanh hơn (vì chỉ tới căn bậc 2 của upperRange)

toàn bộ code Sieve

void sieve(int n)
{
	int i,j;
	sieveSize = n + 1;
	for (i = 0;i <= sieveSize;++i) prime[i] = 1;
	for (i = 2;i * i<= sieveSize;++i)
		if (prime[i] == 1)
			for (j = i * i;j <= sieveSize;j += i;) prime[j] = 0;
	prime[0] = prime[1] = 0;
}

Ngắn gọn hợp thời trang ^_^

[DoQuan]

Từ 1 tới 40 triệu tìm đc 20 triệu số trong 1s .

Em sửa như này được không nhỉ?

#include<iostream>
#include<time.h>//thuat toan tim so nguyen to toi uu

void findPrime(int lowerRange , int upper);
int main(){
int n,m;
clock_t t;
std::cout<<"Enter m: ";std::cin>>m;
std::cout<<"Enter n: ";std::cin>>n;
t = clock();
findPrime(m,n);
t = clock() - t;
std::cout<<"The program run in "<<(((float)t)/CLOCKS_PER_SEC)<<"seconds"<<std::endl;
return 0;
}
void findPrime(int lowerRange , int upper){
int count =0,t,d,k;
int upperRange = upper +1;
clock();// t,d;
t=clock();
bool * eraTos = new bool[upperRange];

for(int i = 0 ; i < upperRange ; i++){
eraTos[i] = true;
}
int maxRange;
for(int i = 2; i <= upperRange/2 ; i++){
maxRange = upperRange / i;
if(eraTos[i] == true){
for (int j = 2 ; j <= maxRange ; j++){
eraTos[j*i] = false;
}
}
}
for(int i = lowerRange; i < upperRange; i++){
if(eraTos[i] == true){
//std::cout<<i<<" "; //in ra so nguyen to
count++;
}
}
std::cout<<"\n"<<"Found "<<count<<" prime ";

}

public static void getNumbers(int lowerRange , int upper){
		int upperRange = upper +1;
		boolean[] sieve = new boolean[upperRange];
		for(int i = 0 ; i < upperRange ; i++){
			sieve[i] = true;	
		}	
		int maxRange;
		for(int i = 2; i <= upperRange/2 ; i++){
			maxRange = upperRange / i;
			if(sieve[i] == true){
				for (int j = 2 ; j < maxRange ; j++){
					sieve[j*i] = false;
				}
			}
		}
		for(int i = lowerRange; i <  upperRange; i++){
			if(sieve[i] == true){
				System.out.print( i + "   ");
			}
		}
		
		
	}

Vẫn còn dính con số cuối chưa set false được , tối về sửa , giờ đi thi sinh viên khỏe :-)

[sinhvien.uit]

Em sửa như này được không nhỉ?

Code xấu quá không coi cơ mà từ 1 đến 40 triệu lại có tới tận 20 triệu số nguyên tố. Như vậy trung bình 2 số thì 1 số là số nguyên tố! VÔ LÝ!