Đếm Các Số Nguyên Tố Trong Dãy
Đề bài
ĐẾM CÁC SỐ NGUYÊN TỐ TRONG DÃY
Cho dãy số $A$ có $n$ phần tử chỉ bao gồm các số nguyên dương (không quá $10^5$). Hãy xác định các số nguyên tố trong dãy và đếm xem mỗi số xuất hiện bao nhiêu lần.
Input: Dòng đầu tiên ghi số bộ test. Với mỗi bộ test: dòng đầu ghi số $n$ (không quá $100$); dòng tiếp theo ghi $n$ số của dãy.
Output: Với mỗi bộ test ghi ra thứ tự bộ test, sau đó lần lượt là các số nguyên tố trong dãy theo thứ tự từ nhỏ đến lớn và số lần xuất hiện của nó.
1
10
1 7 2 8 3 3 2 1 3 2Test 1:
2 xuat hien 3 lan
3 xuat hien 3 lan
7 xuat hien 1 lanLời mở đầu
Bài tập hôm nay: liệt kê các số nguyên tố phân biệt theo giá trị tăng dần kèm theo tần suất xuất hiện của chúng trong mảng 1 chiều các số nguyên. Một bạn học viên gửi bài làm cho mình và hỏi: "tối ưu được cái gì không anh, với có cách khác không ạ, bài em hơi dài á". Vậy là mình góp ý bài làm của em, chỉ ra những chỗ chưa tối ưu và hướng dẫn em tối ưu lại. Mình viết lại thành bài giải để các bạn mới học mảng 1 chiều cùng tham khảo nha 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJGiải thích ví dụ: dãy 1 7 2 8 3 3 2 1 3 2 có các số nguyên tố là 7, 2, 3, 3, 2, 3, 2 (số 1 và số 8 không phải số nguyên tố). Số 2 xuất hiện 3 lần, số 3 xuất hiện 3 lần, số 7 xuất hiện 1 lần. In theo thứ tự tăng dần là 2, 3, 7; và nhớ in dòng Test 1: trước nhé.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Bài làm của học viên – chính xác nhưng chưa tối ưu
Ý tưởng của em hiện tại là dùng 2 mảng: 1 mảng (phu1) lưu tất cả các số nguyên tố có trong dãy, 1 mảng (phu) chỉ lưu các số nguyên tố phân biệt. Xong rồi em đi sắp xếp mảng các số nguyên tố phân biệt tăng dần, rồi thì đếm từng phần tử trong mảng phân biệt với mảng trùng xem từng phần tử đó xuất hiện bao nhiêu lần, sau đó in ra kết quả.
Test k:), em chưa xử lý phần số bộ test nên nhớ lưu ý hen. Code bên dưới mình đã bổ sung phần này.Còn nếu xét riêng phần xử lý trên dãy $N$ số này của em thì như hiện tại em làm vậy cũng được, về mặt chính xác thì đồng ý nó chính xác. Tuy nhiên tối ưu thì còn nhiều chỗ chưa tối ưu, để mình phân tích ra:
- Hàm kiểm tra số nguyên tố chưa tối ưu. Em đang thử ước từ 2 tới $a / 2$, trong khi chỉ cần thử tới $\sqrt{a}$ là đủ. Với $a \approx 10^5$ là chênh nhau cỡ $50000$ lần lặp so với khoảng $316$ lần lặp. Phần này các bạn có thể tham khảo thêm bài viết "Kiểm tra 1 số có là số nguyên tố không?" của mình để hiểu rõ vì sao chỉ cần tới căn nhé.
- So trùng trên mảng ban đầu. Ngay từ bước kiểm tra để chỉ nhận các số nguyên tố phân biệt đưa vào mảng phân biệt, theo code em hiện tại là đi so sánh thằng
a[i]hiện tại với tất cả các thằnga[j]ở trước nó xem có thằng nào khiến bị trùng không. Em đang so sánh trên mảng ban đầu là 1 sai lầm lớn vì nó quá phức tạp. Tại sao không so sánh trên mảng đang chứa các số nguyên tố phân biệt? Vì trong mảng ban đầu có cả những số không phải nguyên tố, tại sao phải mất công xét với cả những thằng ấy? Mình chỉ cần đang xét với những thằng thoả là nguyên tố đã tìm thấy xem thằng hiện tại có bị trùng không mà. Chỗ này sửa sẽ giảm được nhiều số lần so sánh hơn. - Bước đếm số lần xuất hiện. Em tưởng tượng thử nhé: giả sử trong nguyên dãy có 100 số toàn là nguyên tố và chỉ có 10 số nguyên tố phân biệt, nghĩa là mỗi số sẽ bị lặp lại 10 lần. Theo cách làm này của em, mỗi số nguyên tố phân biệt trong 10 số phải chạy so sánh hết với mảng 100 số nguyên tố, như thế thì cả thảy $10 \times 100 = 1000$ lần xét duyệt.
Code của em (mình chỉ sắp lại cho gọn, giữ nguyên logic, và bổ sung phần đọc số bộ test):
#include <iostream>
using namespace std;
#define MAX 105
void Nhap(int a[], int n)
{
for (int i = 0; i < n; i++)
cin >> a[i];
}
bool KiemTraSoNguyenTo(int a)
{
if (a < 2)
return false;
else if (a > 2)
{
if (a % 2 == 0)
return false;
else
{
for (int i = 2; i <= a / 2; i++)
{
if (a % i == 0)
return false;
}
}
}
return true;
}
void XuLy(int a[], int n)
{
int phu[MAX], phu1[MAX];
int index = 0, index1 = 0;
if (KiemTraSoNguyenTo(a[0]) == true)
{
phu1[index1++] = a[0];
phu[index++] = a[0];
}
for (int i = 1; i < n; i++)
{
if (KiemTraSoNguyenTo(a[i]) == true)
{
phu1[index1++] = a[i];
bool check = true;
for (int j = i - 1; j >= 0; j--)
{
if (a[i] == a[j])
{
check = false;
}
}
if (check == true)
phu[index++] = a[i];
}
}
// sắp xếp tăng dần
for (int i = 0; i < index - 1; i++)
{
int min = i;
for (int j = i + 1; j < index; j++)
{
if (phu[j] < phu[min])
{
min = j;
}
}
swap(phu[i], phu[min]);
}
for (int i = 0; i < index; i++)
{
int dem = 0;
for (int j = 0; j < index1; j++)
{
if (phu[i] == phu1[j])
{
dem++;
}
}
cout << phu[i] << " xuat hien " << dem << " lan" << endl;
}
}
int main()
{
int t;
cin >> t;
for (int k = 1; k <= t; k++)
{
int a[MAX];
int n;
cin >> n;
Nhap(a, n);
cout << "Test " << k << ":" << endl;
XuLy(a, n);
}
return 0;
}def kiem_tra_so_nguyen_to(a):
if a < 2:
return False
elif a > 2:
if a % 2 == 0:
return False
for i in range(2, a // 2 + 1):
if a % i == 0:
return False
return True
def xu_ly(a, n):
phu = [] # các số nguyên tố phân biệt
phu1 = [] # tất cả các số nguyên tố (kể cả trùng)
for i in range(n):
if kiem_tra_so_nguyen_to(a[i]):
phu1.append(a[i])
check = True
for j in range(i - 1, -1, -1):
if a[i] == a[j]:
check = False
if check:
phu.append(a[i])
# sắp xếp tăng dần (selection sort)
for i in range(len(phu) - 1):
mn = i
for j in range(i + 1, len(phu)):
if phu[j] < phu[mn]:
mn = j
phu[i], phu[mn] = phu[mn], phu[i]
for x in phu:
dem = 0
for y in phu1:
if x == y:
dem += 1
print(x, "xuat hien", dem, "lan")
data = list(map(int, open(0).read().split()))
p = 0
t = data[p]; p += 1
for k in range(1, t + 1):
n = data[p]; p += 1
a = data[p:p + n]; p += n
print("Test " + str(k) + ":")
xu_ly(a, n)Đánh giá độ phức tạp của cách làm này (mỗi bộ test, $V$ là giá trị lớn nhất):
- Kiểm tra nguyên tố: $O(n \cdot V)$ trong trường hợp xấu (thử ước tới $V / 2$).
- So trùng trên mảng gốc: $O(n^2)$; sắp xếp chọn: $O(k^2)$ với $k$ là số nguyên tố phân biệt; đếm: $O(k \cdot p)$ với $p$ là số lượng số nguyên tố.
Cách 2Vừa so trùng vừa đếm luôn: 2 mảng song song – O(n·√V + n²)
Có 1 cách tốt hơn, em suy nghĩ thử theo hướng này nhé. Đằng nào mỗi khi ta gặp 1 số nguyên tố trong dãy $A$ ban đầu, ta cũng phải duyệt lại trong mảng đang chứa các số nguyên tố phân biệt xem coi thằng số nguyên tố vừa tìm được có bị trùng không đúng không? Để nếu không trùng thì ta đem nó bỏ vào mảng các số nguyên tố phân biệt, còn nếu trùng thì ta bỏ qua không lấy.
Thử trên giấy nháp
Ví dụ cho dãy số: 1 7 2 8 3 3 2 1 3 2, các bạn ghi dãy số này ra tờ giấy nháp rồi thử hen. Bắt đầu xét dãy số từ trái qua phải; để tượng trưng số lần xuất hiện mình sẽ ghi nó trong dấu ngoặc, ví dụ 7 (1) là số 7 đang xuất hiện 1 lần (trên giấy thì các bạn đánh một số 1 nhỏ lên đầu số 7):
a[0] = 1⇒ bỏ qua vì không phải số nguyên tố.a[1] = 7⇒ đây là số nguyên tố. Kiểm tra xem 7 có xuất hiện trong mảng chứa các số nguyên tố phân biệt chưa? Lúc này mảng đang rỗng, nghĩa là thằng 7 này sẽ yên tâm không bị trùng với thằng nào hết (vì nó là thằng đầu tiên mà) ⇒ đưa nó vào mảng:7 (1).a[2] = 2⇒ là số nguyên tố, so với mảng đang có mỗi số 7 ⇒ không bị trùng ⇒ đưa vào:7 (1), 2 (1).a[3] = 8⇒ bỏ qua vì đây không phải số nguyên tố.a[4] = 3⇒ là số nguyên tố, số 3 chưa xuất hiện ⇒ đưa vào:7 (1), 2 (1), 3 (1).a[5] = 3⇒ số 3 đã xuất hiện rồi ⇒ không đưa vào nữa, nhưng cập nhật số lần xuất hiện của nó +1:7 (1), 2 (1), 3 (2).a[6] = 2⇒ số 2 đã xuất hiện ⇒ +1:7 (1), 2 (2), 3 (2).a[7] = 1⇒ bỏ qua.a[8] = 3⇒ +1:7 (1), 2 (2), 3 (3).a[9] = 2⇒ +1:7 (1), 2 (3), 3 (3).
Rồi lúc này mảng $a$ đã hết phần tử để xét. Đi sắp xếp nó theo giá trị số nguyên tố tăng dần ta được: 2 (3), 3 (3), 7 (1). 🎉
Cài đặt chỉ với mảng 1 chiều
Về mặt lý thuyết nói là vậy, nhưng giờ hiện thực cho máy tính nó hiểu mà làm đúng như vậy được: trên giấy thì em "đánh số 1 nhỏ lên đầu" của từng số trong mảng các số nguyên tố phân biệt, nhưng máy tính đâu có đánh kiểu đó được :)) Bạn học viên nghĩ ngay tới struct – ok struct cũng được đó, gọn 👍, nhưng nếu giả sử bài này chưa học đến đó thì đâu được phép dùng; bài này chỉ đang là mảng 1 chiều thôi.
A để lưu các số nguyên tố phân biệt, 1 mảng B để lưu tần suất xuất hiện của các số tương ứng trong mảng A: B[i] là số lần xuất hiện của số nguyên tố A[i]. Khi sắp xếp mảng A tăng dần, cần hoán vị 2 số ở vị trí nào thì ta cũng hoán vị 2 số tại vị trí tương ứng trong mảng B. Xong rồi duyệt mảng A tăng dần, xét đến A[i] thì gọi ra B[i] chính là số lần xuất hiện tương ứng.Thực ra ở chỗ này mình đã cố gắng gợi mở cho em hướng 2 mảng song song – đơn giản hơn nhiều – nhưng có vẻ em ấy không nhận ra ^^. Code bên dưới là theo hướng 2 mảng song song đó, kèm hàm kiểm tra nguyên tố chỉ thử ước tới căn.
Minh hoạ
Em nhập dãy số rồi bấm Tiếp để xem 2 mảng A (số nguyên tố phân biệt) và B (số lần xuất hiện) được xây dựng ra sao, rồi được sắp xếp "đi cả bộ" thế nào:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <iostream>
using namespace std;
#define MAX 105
bool KiemTraSoNguyenTo(int x)
{
if (x < 2)
return false;
for (int i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
int main()
{
int t;
cin >> t;
for (int k = 1; k <= t; k++)
{
int n, a[MAX];
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
int A[MAX], B[MAX], m = 0;
for (int i = 0; i < n; i++)
{
if (!KiemTraSoNguyenTo(a[i]))
continue;
int j = 0;
while (j < m && A[j] != a[i])
j++;
if (j < m)
B[j]++;
else
{
A[m] = a[i];
B[m] = 1;
m++;
}
}
for (int i = 0; i < m - 1; i++)
for (int j = i + 1; j < m; j++)
if (A[j] < A[i])
{
swap(A[i], A[j]);
swap(B[i], B[j]);
}
cout << "Test " << k << ":" << endl;
for (int i = 0; i < m; i++)
cout << A[i] << " xuat hien " << B[i] << " lan" << endl;
}
return 0;
}def kiem_tra_so_nguyen_to(x):
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
data = list(map(int, open(0).read().split()))
p = 0
t = data[p]; p += 1
for k in range(1, t + 1):
n = data[p]; p += 1
a = data[p:p + n]; p += n
A = [] # các số nguyên tố phân biệt
B = [] # B[j] = số lần xuất hiện của A[j]
for x in a:
if not kiem_tra_so_nguyen_to(x):
continue
j = 0
while j < len(A) and A[j] != x:
j += 1
if j < len(A):
B[j] += 1
else:
A.append(x)
B.append(1)
m = len(A)
for i in range(m - 1):
for j in range(i + 1, m):
if A[j] < A[i]:
A[i], A[j] = A[j], A[i]
B[i], B[j] = B[j], B[i]
print("Test " + str(k) + ":")
for i in range(m):
print(A[i], "xuat hien", B[i], "lan")Đánh giá độ phức tạp của cách làm này (mỗi bộ test, $V \le 10^5$ là giá trị lớn nhất, $k$ là số số nguyên tố phân biệt):
- Kiểm tra nguyên tố: mỗi số thử ước tới căn ⇒ $O(n\sqrt{V})$, cỡ $100 \times 316$ phép tính.
- Tìm trùng + đếm: mỗi số nguyên tố chỉ duyệt trên mảng $A$ gồm $k$ số phân biệt ⇒ $O(n \cdot k)$, và việc đếm làm luôn trong lúc tìm, không tốn thêm vòng lặp nào.
- Sắp xếp: sắp xếp đơn giản $O(k^2)$; $k \le n \le 100$ nên rất nhẹ.
cnt[100001]: gặp số nguyên tố $x$ thì cnt[x]++, cuối cùng duyệt $x$ từ 2 tới $10^5$, gặp cnt[x] > 0 thì in – vừa khỏi tìm trùng vừa khỏi sắp xếp (nhớ reset mảng đếm cho mỗi bộ test). Nhưng với giới hạn kiến thức của bài là mảng 1 chiều cơ bản thì hướng 2 mảng song song ở trên là đủ tốt và rất dễ hiểu rồi.Counter – khớp hết. Với 100 bộ test, mỗi bộ 100 số nguyên tố cỡ $10^5$ (đề không ghi giới hạn số bộ test, mình tự chọn để thử): cách 1 (C++) chạy khoảng 1.7 giây, bản Python của cách 1 tới khoảng 51 giây – chủ yếu do hàm kiểm tra nguyên tố thử ước tới $a / 2$; còn cách 2 (C++) chỉ khoảng 0.03 giây, Python khoảng 0.5 giây.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét