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

[08520001]

Mình xin mở đầu với 1 bài tập đơn giản:
Hãy tìm tất cả các số nguyên tố trong đoạn [A,B] .
Input
Gồm 2 số nguyên A và B cách nhau bởi 1 dấu cách ( 1 ≤ A ≤ B ≤ 200000 ) .
Output
Ghi ra tất cả các số nguyên tố trong khoảng [A,B]. Mỗi số trên 1 dòng .
Ví dụ

Input:
1 10

Output:
2
3
5
7

Giới hạn thời gian: 1s
Mời các bạn nhé do lot nu.

[10520355]

bool nguyento(int t)
{
for(int i=2; i<t; i++)
if(t%i==0) return false;
return true;
}
for(int i=a; i<=b; i++)
if(nguyento(i)) cout<<i<<endl;

[10520355]

anh An ơi. em hâm mộ anh lắm. Hi. trùng hợp là hai anh em mình còn trùng họ nữa. keke

[08520001]

hi. Trùng hợp nhỉ. Hix. Sao hok ai làm được bài này vậy nhỉ? Buồn thiệt do lot nam.

[08520604]

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 :-)

[BiThuDoan]

Chỉ có cách sàng là nhanh nhất hay sao?

[09520019]

Anh An cho thêm cái yêu cầu : thời gian chạy - 1s đi ^_^
Thầy Toàn ơi gợi ý lộ liễu quá thầy :-ss

[08520604]

Anh An cho thêm cái yêu cầu : thời gian chạy - 1s đi ^_^
Thầy Toàn ơi gợi ý lộ liễu quá thầy :-ss

Đúng cái mình thắc mắc , thường thì các bài toán có đưa ra giới hạn chẳng hạn như t <= 1s , memory <=16MB chẳng hạn , nếu là giới hạn về bộ nhớ thì
có thể hiểu , nhưng giới hạn về thời gian thì phụ thuộc vào mẫu N đưa vào cơ mà , hay là giới hạn của t này là áp dụng cho trường hợp xấu nhất , chẳng hạn
với bài toán trên là khi tìm trong khoảng ( 1 --> 200000). :-s

[09520019]

bài này 1s đc mà, với lại cách anh Toàn post là cỏ vẻ < 1s rồi đấy... (mặc dù chưa tối ưu nhất có thể)

[07520004]

Đúng cái mình thắc mắc , thường thì các bài toán có đưa ra giới hạn chẳng hạn như t <= 1s , memory <=16MB chẳng hạn , nếu là giới hạn về bộ nhớ thì
có thể hiểu , nhưng giới hạn về thời gian thì phụ thuộc vào mẫu N đưa vào cơ mà , hay là giới hạn của t này là áp dụng cho trường hợp xấu nhất , chẳng hạn
với bài toán trên là khi tìm trong khoảng ( 1 --> 200000). :-s

Cách giải của chú thì N và M có là 1->20000 hay là 199999 -> 200000 thời gian nó cũng như nhau thôi mà . Nhưng mà cũng < 1s rồi, 200000 nhỏ quá, nếu chạy thực tế nó không được thì đổi qua C++ đi, đừng có chơi C# =))

[08520604]

bài này 1s đc mà, với lại cách anh Toàn post là cỏ vẻ < 1s rồi đấy... (mặc dù chưa tối ưu nhất có thể)

Ủ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 :-)

[08520604]

Cách giải của chú thì N và M có là 1->20000 hay là 199999 -> 200000 thời gian nó cũng như nhau thôi mà . Nhưng mà cũng < 1s rồi, 200000 nhỏ quá, nếu chạy thực tế nó không được thì đổi qua C++ đi, đừng có chơi C# =))

Em ấy nó bằng java đó ạ , đâu phải C# đâu anh

[07520004]

Em ấy nó bằng java đó ạ , đâu phải C# đâu anh

Ợ ợ, thế thì lâu hơn 1s là cái cẳng

[08520001]

Hi. Không hẳn đâu. Với bài này thì dùng sàng Eratosthenes là ok rồi. Hi. Xem như bài này đã giải xong. Chúng ta tạm đóng topic ở đây vậy quan ao nu

[08520604]

Lót dép ngồi hóng bài tiếp theo :-)