Xuất các số nguyên tố trong mảng bất kỳ gồm n phần tử

Mình chào các bạn, giờ mình có một chương trình nhập vào một mảng bất kỳ gồm n phần tử, yêu cầu là phải xuất ra các số nguyên tố trong mảng đó, mình đã viết được rồi nhưng vẫn chưa tối ưu hết các trường hợp như: Nhập vào 2.0 thì không xuất vì không phải là số nguyên tố còn khi nhập vào 2 thì xuất ra vì là số nguyên tố, mong các bạn giúp mình với, mình xin cảm ơn.

Bạn đưa code lên để mọi người cùng sửa cho nha. :slight_smile:

3 Likes
#include<stdio.h>
#include<conio.h>
#include<math.h>

void nhapmang(float A[],int n)
{
	for(int i=0;i<n;i++)
	{
		printf("Nhap A[%d]=",i);
		scanf("%f",&A[i]);
	}
}
void xuatmang(float A[],int n)
{
	for(int i=0;i<n;i++)
	printf(" %6.2f ",A[i]);
}
int snt(float n)
{
	if(n<2) return 0;
	if(n==(int)n)
	{
		for(int k=2;k<=sqrt(n);k++)
	    {
	    	if((int)n%k==0) return 0;
	    	else return 1;
		}
	}
	else return 0; 
}
main()
{
	int n;
	float A[100];
	printf("Nhap so phan tu n=");
	scanf("%d",&n);
	nhapmang(A,n);
	printf("Mang A la:");
	xuatmang(A,n);
	printf("\nCac so nguyen to trong mang A la:");
	for(int i=0;i<n;i++)
	{
		if(snt(A[i])) printf(" %6.2f ",A[i]);
	}
}
Edit code

Chưa ổn lắm, chú ý cách sử dụng ifreturn nha bạn.
Trong if đầu tiên nên kết hợp cả if thứ 2. Thành:

	if(n < 2 || n != (int)n)
		return 0;

Và bỏ if thứ 2 đi. Còn nữa trong for không cần cho else retrun 1, Vì:

  • Chỉ cần kiểm tra xem n có chia hết cho i: có :point_right: return 0 (k cần else).
  • Hết for thì return 1.

Sửa lại cho bạn:

int snt(float n) {
	if(n < 2 || n != (int)n)
		return 0;
	for(int k=2; k<=sqrt(n); k++) {
		if((int)n%k==0)
			return 0;
	}
	return 1;
}

Tối ưu hóa code

Nhưng ta không cần thiết phải kiểm tra hết các số từ 2 cho đến \sqrt{n} mà chỉ cần kiểm tra các số có dạng 6k\pm 1 trong khoảng từ 5 cho đến \sqrt{n} với n > 5.

Hay hiểu đơn giản là kiểm tra xem n có chia hết cho các số nguyên tố nhỏ hơn \sqrt{n} không.

Đây là code cho bạn:

int isPrime(float a) {
	if (a < 1 || a != (int)a)
		return 0;
	int k = -1, n = (int)a;
	if ((1 <= n && n <= 3) || n == 5)
		return 1;
	if (!(n % 2) || !(n % 3))
		return 0;
	while (k * k <= n) {
		k += 6;
		if (!(n % k) || !(n % (k + 2)))
			return 0;
	}
	return 1;
}

Chưa phải là tối ưu nhất nhưng cũng khá ổn. :slight_smile:

4 Likes

Hàm này nếu cho a=2.0 thì nó sẽ kiểm tra có phải số nguyên tố không ạ?

Cả hàm của bạn trc đó mình cũng test r, nhập 2.0 vẫn là snt nha bạn.
Có thể là do máy bạn chăng. :thinking:

3 Likes

À không, ý của mình là làm sao để kiểm tra 2.0 không phải số nguyên tố còn 2 là số nguyên tố vì số thực không thể là số nguyên tố được.

Huh?
Số thực? Tập số nguyên nằm trong tập số thực :point_right: 2 là số nguyên nhưng cũng là số thực. Hay bạn có thâm thù gì với số 2.0 :laughing:


Còn thực tế bạn đã để kiểu của nó là float dù bạn có nhập 2 hay 2.0 thì nó cũng như nhau thôi.

Nếu muốn hàm được như bạn nói thì bạn nên lưu dạng string. Rồi ép về intfloat.

3 Likes

Mình cx biết là vậy nhưng thầy của mình yêu cầu là khi thầy nhập 2 2.0 3 3.0 thì tổng các số nguyên tố phải bằng 5, nếu mà bằng 10 là sai, bạn có cách nào không, giúp mình vs.

Ví dụ hơi mơ hồ. Có thể có 2 cách hiểu sau đây:

  • Trong dãy trên tuy có 4 số nhưng chỉ có 2 số nguyên tố là 2 và 3. Nghĩa là 2 và 2.0 cho số nt 2, 3 và 3.0 cho số nguyên tố 3. (nghĩa là cùng chỉ đến 1 số nguyên tố thì chỉ lấy 1 số).

  • Cách hiểu thứ 2 thì như bạn hiểu là 2.0 và 3.0 không phải số nguyên tố.

Nhưng mình thiên về cách thứ nhất nhiều hơn. Bạn có thể quote nguyên đề bài được không nhỉ, thêm những ví dụ rõ ràng hơn nữa. :slight_smile:

3 Likes

Nhập một mảng A gồm n phần tử. Tính tổng các số nguyên tố trong A.

Khi chạy chương trình, thầy sẽ nhập ngẫu nhiên như: 2 2.1 19 5.0 6 7 3.0 3 thì khi đó tổng các số nguyên tố là 31 là đúng còn chương trình của mình cho ra là 39 thì thầy bảo sai còn nói là phải chia thành 2 trường hợp số nguyên vs số thực để xét, nếu nhập vào số thực dù là 2.0 hay là 2.1 cx bị lọc ra, chỉ chấp nhận số thuần nguyên như là 2 3 thôi.

Mình cũng có nói thầy như bạn là tập hợp số nguyên nằm trong tập hợp số thực thì thầy nói đó là toán còn lập trình là phải phân biệt rõ ràng: 2 kiểu int khác 2.0 kiểu float.

Thì như mình nói :point_up_2: mà làm thôi.

  • Bạn sẽ phải sửa lại mảng float A[] thành char A[][100]. (Để lưu số bạn nhập ở dạng chuỗi)

  • Bạn sẽ cần một hàm gọi là isInt() để kiểm tra xem nó có phải là số nguyên không. Và xử lý + loại luôn trường hợp nếu là số thực.

  • Nếu là số nguyên rồi bạn lại phải có một hàm s2i() để chuyển từ char[] sang int.

Hàm kiểm tra là số nguyên.
int isInt(const char *s) {
	int size = strlen(s);
	int i = 0;
	while (i < size) {
		if (s[i] < '0' || s[i] > '9')
			break;
		i++;
	}
	return i == size;
}
Hàm chuyển đổi string sang int
int s2i(const char *s) {
	int size = strlen(s);
	int integer = 0, i = 0;
	while (i < size) {
		if (s[i] < '0' || s[i] > '9')
			break;
		i++;
	}
	for (int j = 0; j < i; j++)
		integer = 10 * integer + s[j] - '0';
	return integer;
}

Mình lười viết nốt :sweat_smile: cho nên để phần còn lại cho bạn.
Các hàm cho bạn tham khảo thì ở :point_up_2: là đủ rồi . :smile:

3 Likes

Thế thì khi mình xuất mảng A ra thì để định dạng %s à?

Bạn chưa đọc hàm s2i() nhỉ. :sweat_smile: Tuy nhập vào A[]%s nhưng bạn vẫn xuất ra dạng %d bình thường vì s2i() trả về kiểu int mà, và bạn cũng dùng giá trị này để đưa vào hàm isPrime() like this :point_right: if (isPrime(s2i(A[i])) printf("%d", s2i(A[i]));

Hoặc bạn có thể tạo một mảng B[] để lưu những giá trị là số nguyên của mảng A[]. :slight_smile:

3 Likes

OK, chương trình của mình chạy được rồi, cảm ơn bạn nhiều nha :grinning:

1 Like

học cùng thầy cmnr.
Bạn trên hướng dẫn tận tình vậy rồi mà. Bạn đọc hd của bạn đó rồi làm theo đi :slight_smile:

Hello bạn, để mình tìm thử coi còn 0, tại lâu quá rồi, mà bạn học bkđn phải 0 z?

2 Likes

Haha chào bro , em cũng BKĐN nè , nhìn vụ 2.0 nguyên tố nghĩ ngay đến Mr.Nguyên chứ đâu :v , bài này em viết hàm để kiểm tra số thực , trong đó có sử dụng hàm Isdigit của ctype,h , hoặc căng lắm tự viết hàm Isdigit đó luôn :v

2 Likes

Mọi thảo luận của mình với @Huynh2 đều vẫn còn ở trên, bạn có thể cho mình biết tại sao bạn không chịu bỏ chút thời gian ra để đọc được không nhỉ. :smiley:

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