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

quan1011 · November 15, 2019, 10:31am

chào mọi người hiện tại em đang làm bài toán liệt kê số nguyên tố nhỏ hơn n (n nhập từ bàn phím ), em hiện tại đã code xong nhưng không rõ sai đâu mà lúc chạy nó hiện kết quả như hình dưới. Mong mọi người giải đáp em cảm ơn

#include <stdio.h>
int nguyento(int n)
{	
	int i;
	for (i=2;i<=n;i++)
			if (n%i==0)
				{
					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;	
}

noname00 · November 15, 2019, 10:34am

Dù sao thì topic này cũng lại trồi lên rồi, mình move thẳng code ở post #4 lên post #1 (thay thế cho hình), còn những post khác về up code thì mình move sang off-topic.

Evil_Artist · May 22, 2018, 12:45am

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é.

quan1011 · May 22, 2018, 1:19am

đạ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;
}

Asterick · May 22, 2018, 2:38am

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.

quan1011 · May 22, 2018, 2:42am

đạ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

Evil_Artist · May 22, 2018, 2:45am

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

quan1011 · May 22, 2018, 3:08am

à 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

namhaiha0308 · May 22, 2018, 10:30am

Đã 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;
}

Nguyen_Phu_Thanh · May 22, 2018, 10:43am

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 đã

quan1011 · May 22, 2018, 10:44am

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

namhaiha0308 · May 22, 2018, 10:51am

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

Nhan_Nguyen9 · July 4, 2019, 6:42am

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

rogp10 · July 4, 2019, 6:55am

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

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.

Nhan_Nguyen9 · July 30, 2019, 8:13am

thank you bạn nhiều nha

Trung_Rua · November 15, 2019, 10:27am

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

rogp10 · November 15, 2019, 11:22am

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

hoangltse04739 · November 15, 2019, 2:30pm

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

Thanh_Nha · December 8, 2019, 10:46am

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

8_Naf · December 8, 2019, 3:30pm

tối ưu code lại chút nè

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

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

	//So chẵn khác 2 không phải là số nguyên tố
	//Số bé hơn 2 không phải là 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);
		}
	}
}