Bài toán liệt kê số nguyên tố nhỏ hơn n trong c

Bài này mắc lỗi sai cực kỳ nghiêm trọng ở hàm

int nguyento(int n)

còn lại tự debug và sửa lỗi nhé.

2 Likes

đại khái sau khi fix thì vẫn không chạy được ạ

int nguyento(int n)
{	
	int i;
	for (i=2;i<=n;i++)
			if (n%i==0)
				{
					return 0;
					break;
				}
	return 1;
}

Vấn đề ở đây là algorithm của bạn sai hoàn toàn rồi (bạn nên check lại logic của bạn trên giấy trước khi viết nó trên máy tính nha)

Hint: bạn muốn kiếm all prime numbers < n thì công thức toán Sieve of Eratosthenes là điểm khởi đầu tốt cho bạn đấy.

Good luck.

7 Likes

đại khái mình vẫn chưa rõ giải thuật sai ở đâu, đại khái là mình kiểm tra 1 số n có phải là số nguyên tố không, thì cho i chạy từ 2 đến n, nếu n chia hết cho i thì trả về giá trị 0 ( tức là không phải số nguyên tố), nếu không phải thì trả về giá trị 1. Và nếu hàm trả về giá trị 1 thì in i ra màn hình

Hãy test làm nguyento trước với 1 số nguyên tố (vd 5) và 1 số không nguyên tố (vd 4).
Trong câu

if(n%i==0) 

In ra màn hình

"%d chia het cho %d", n, i

Kiểm tra kết quả để biết sai ở đâu

1 Like

à rồi cảm ơn bác, tại xét <=n trong vòng lặp for của hàm nên ra kết quả sai

Đã sửa lại cho bạn nè, đã tối ưu hóa thuật toán để không phải lặp nhiều.

#include <stdio.h>
#include <math.h>
int nguyento(int n)
{
    int i;
    for (i = 2; i <= (int)sqrt(n); i++)
        if (n % i == 0 and n != i)
        {
            return 1;
            break;
        }
}
int main(void)
{
    int i, n, kt;
    printf("Nhap vao so nguyen n: ");
    scanf("%d", &n);
    printf("\nCac so nguyen to nho hon n la: ");
    for (i = 2; i <= n; i++)
        if (nguyento(i) != 1)
            printf("%d ", i);
    return 0;
}

người ta nhập vào số <2 thì sao ? tối ưu code là việc làm sau cùng trước hết là phải tìm hết các trường hợp có thể xảy ra cái đã

3 Likes

cảm ơn bác, với cả mình cũng đã sửa lại bài để tính các trường hợp < 2 rồi

1 Like

Cảm ơn bác đã nhắc nhở. <3

1 Like

bạn cho mình hỏi tại sao n%i==0
với tại sao bạn dùng hàm sqrt vậy. mình thấy không có sqrt nó cũng ra kết quả ấy.thanks

Câu này nghĩa là “n chia hết cho i” :smiley:

Bởi vì vượt quá sqrt tức là nguyên tố rồi.

Khi p * q = n thì có p mới có q, và ngược lại. Thừa số nhỏ hơn sẽ không quá căn n vì nếu không, tích hai số sẽ lớn hơn n, mâu thuẫn.

4 Likes

thank you bạn nhiều nha

kt ở hàm chính là gì vậy m.n ơi?

Bạn vui lòng quote trực tiếp nhé :smiley:

3 Likes

Bạn đã return 1 lúc kiểm tra rồi thì không cần break; nữa

3 Likes

snt
mọi người cho em hỏi e sai chỗ nào ạ???
e chạy nó không ra kết quả ạ

tối ưu code lại chút nè

//using -std=c11
#include <stdio.h>
#include <stdbool>
#include <math.h>

bool is_prime (int n) {
	if (2 == n) {
		return true;
	}

	//So chẵn khác 2 không phải là số nguyên tố
	//Số bé hơn 2 không phải là số nguyên tố
	if (n < 2 || 0 == n%2) {
		return false;
	}

	size_t end = (size_t) sqrt(n);

	for (size_t i = 3; i <= end; i += 2) {
		if (0 == n%i) {
			return false;
		}
	}
	
	return true;
}
int main() {
	printf("Nhap vao so nguyen n: ");
	int n;
	scanf("%d", &n);
	

	printf("\nCac so nguyen to nho hon %d la: \n", n);

	if (n > 2) {
		printf("2 ");
	}

	for (int i = 3; i < n; i += 2) {
		if (is_prime(i)) {
			printf("%d ", i);
		}
	}
}
4 Likes

Số nguyên tố là số có 2 ước 1 và chính nó, bạn chạy từ 2 đến n chẳng phải nó luôn luôn return 0 rồi à :v:

2 Likes

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.

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