Code xuất các số nguyên tố có trong mảng bị sai

#1

Xuất ra các số nguyên tố có trong mảng, yêu cầu:

  • Theo thứ tự tăng dần
  • Chỉ in ra 1 lần cho dù số nguyên tố đó xuất hiện nhiều hơn 1 lần
  • Các số nguyên tố cách nhau bằng 1 dấu cách.

sai ở đâu v ạ

#include <bits/stdc++.h>
using namespace std;
int n,a[10011],res[1011];
int dem=0;
bool cx[1011];
int main(){
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) {
		for (int j=i+1;j=n;j++) {
			if (a[i]>a[j]) swap (a[i], a[j]);
		}
	}
	int cnt=0;
	for (int i=1;i<=n;i++) {
		if (cx[i]==true) {
			cnt++;
			res[cnt]=a[i];
			for (int j=i+1;j<=n;j++) {
				if (a[i]==a[j]) {
					cx[j]=false;
				}
			}
		}
	}
	for (int i=1;i<=n;i++) {
		int x=res[i];
		if (x<2) dem++;
		else {
			for (int j=2;j<=sqrt(x);j++) {
				if (x%j==0) dem++;
			}
		}
	}
	if(dem==0) cout<<dem<<" ";
	return 0;
}
#2

mình cũng mới tập code , đây là bài mình làm , có j k ổn ns mình nha
I’m a newbie @.@

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
bool nguyento(int n)
{
    if (n<=1) return false;
    for (int i=2;i<=sqrt(n);i++)
        if (n%i==0) return false;
    return true;
}
int main()
{
    vector<int> a;
    int n;
    cout<<"Nhập số phần tử trong mảng :  ";cin>>n;
    for (int i=0,j;i<n;i++)
    {
        cout<<"a["<<i+1<<"]:";cin>>j;
        a.emplace_back(j);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    cout<<"Các số nguyên tố theo yêu cầu : ";
    for (int i : a) if (nguyento(i)) cout<<i<<" ";
}

nếu như thấy dư thư viện thì có thể xóa #include <algorithm> rồi sort bằng bubbleSort

#3

Mình chưa xem chi tiết, nhưng sơ qua thì thấy:

  1. Mảng cx bạn chưa hề gán giá trị cho từng phẩn tử trước đó, nhưng vào vòng lặp bạn đã dùng nó để so sánh (if (cx[i]==true)). Ổn không?
  2. Nên tách đoạn mã kiểm tra số nguyên tố ra 1 hàm riêng. Mình thấy có vấn đề với biến dem khi chả thấy bạn gán lại bằng 0 sau mỗi lần lặp.

Ý tưởng thì bạn có thể tham khảo đoạn mã của @caophi562005, nhưng hiện bạn ấy đang dùng rất nhiều lớp/phương thức có sẵn.

  1. Sắp xếp tăng dần
  2. Loại bỏ phần tử trùng. Nhưng thực sự chả cần làm vậy.
  3. Duyệt lần lượt và in ra nếu là số nguyên tố. Nếu bỏ bước 2 thì chỉ cần 1 biến tạm để lưu số đã in ra trước đó, nếu đã in ra thì không in nữa.1
3 Likes
#5

Theo tôi thì khi bạn nhập vào số nguyên tố thì bạn nên viết một hàm sấp xếp bên ngoài hàm main để dễ fix bug và đọc code. Sau khi chắn chắn đã nhập vào số nguyên tố . Nếu muốn chính xác hơn thì bạn nên viết một hàm kiểm tra số nguyên tố trước khi đưa vào mảng . Sau đó gọi hàm xấp sếp là được . Đó là thứ tự các bước để thực hiện yêu cầu bài toán là nhập và số nguyên tố và sấp xếp theo thứ tự tăng dần. Còn hàm kiểm tra số nguyên tố thì có nhiều cách tùy dử liệu đâu vào nhiều hay ít mà bạn sử dụng thuật toán một cách hợp lý.
Đây là một cách kiểm tra số nguyên tố của mình bạn tham khảo:

int prime( int n ){
	for( int i = 2 ; i <= sqrt(n) ; i++){
		if(n % i == 0 ) return 0;
	}
	return n > 1;
}

=> cách này có độ phức tạp của thuật toán là O(nlog(n));

#6

Bạn kiểm tra nguyên tố 1 số bất kì đều tốn O(\sqrt{x}), sau đó gọi n lần để kiểm tra nguyên tố. Vậy riêng công đoạn “kiểm tra nguyên tố n số rồi đưa số nguyên tố vào mảng” đã tốn O(n\sqrt{X}) rồi (X là giá trị max của mảng). Đúng ra thuật toán của bạn có độ phức tạp là O(n\sqrt{X} + n \log n) = O(n \times \max(\sqrt{X}, \log n)).

Trong nhiều trường hợp \sqrt{X} > \log n nên bạn không thể đánh giá độ phức tạp của thuật toán của bạn là O(n \log n) được.

2 Likes
#7

ok cảm ơn bạn đã thảo luận cùng mình , ý mình là thuật toán kiểm tra số nguyên tố của mình đưa ra có độ phức tạp của nó là O(nlog(n)) . Chứ không phải độ phức tạp của cả chương trình .

#8

Riêng cách kiểm tra số nguyên tố của bạn đang duyệt i từ 2 đến sqrt(n) kiểm tra từng số n + sau đó duyệt n từ 2 đến M nào đó để nhét vào mảng, hàm khởi tạo này của bạn đã tốn O(n \sqrt{M}) trước khi bạn kịp chạy cách kiểm tra số nguyên tố trong O(n \log n) rồi bạn.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?