Tìm và in ra các số nguyên tố thỏa mãn đề bài bằng C, thuật toán của mình sai ở đâu?

[piavg]

Mình mới học C ở trường, dc giao một bài tập về nhà với nội dung là

Tìm tất cả các số nguyên tố trong đoạn [1,n] với n nhập từ bàn phím
In các số nguyên tố này ra bàn phím thỏa mãn điều kiện mỗi dòng có soluong (nhập từ bàn phím) số nguyên tố, độ rộng của mỗi số nguyên tố bằng độ rộng của số nguyên tố lớn nhất trong đoạn [1,n] cộng thêm 1 (tức là nếu số lớn nhất có 3 chữ số thì độ rộng của tất cả các số khi in ra đều là 4, số có 1 chữ số thì thêm 3 dấu cách, 2 chữ số thì thêm 2 dấu cách....

Mình có code C thế này

#include <stdio.h>#include <math.h> int main(){    int n, soluong, i=0, j=0, k=0, ntlonnhat=0, dorongi=0, doronglonnhat=0, t=0;     printf("Nhap n : ");    scanf("%d", &n);     printf("Nhap so luong so nguyen to trong 1 dong : ");    scanf("%d", &soluong);     for (i = 2; i<=n; i++) //Tìm ra số nguyên tố lớn nhất trong đoạn [1;n]    {        int dem=0;        for (j=2; j<=sqrt(i); j++)        {            if (i % j == 0)                dem = dem + 1;        }         if (dem == 0)        {            if (i > ntlonnhat)            {                ntlonnhat = i;            }        }    }     while (ntlonnhat >= 1) //Tìm độ rộng lớn nhất, nó bằng độ dài của số nguyên tố lớn nhất        {            ntlonnhat = ntlonnhat / 10;            doronglonnhat = doronglonnhat + 1;        }      for (i = 2; i<=n; i++) //In ra các số nguyên tố với độ rộng thỏa mãn    {        int dem=0;        for (j=2; j<=sqrt(i); j++)        {            if (i % j == 0)                dem = dem + 1;        }         if (dem == 0)        {            printf("%d",i);            while (i>=1)            {                i = i / 10;                dorongi = dorongi + 1;            }            for (t=0; t<=(doronglonnhat-dorongi); t++)            {                printf(" ");            }            k = k + 1;        }        if (k == soluong)            {                k = 0;                printf("\n");            }    }     return 0;}

Khi compile thì ko có lỗi cú pháp nên mình nghĩ là do lỗi thuật toán. Bạn nào biết giúp mình với dc không. Mình lần đầu post bài hỏi nên có gì thiếu sót trong việc trình bày lỗi các bạn nói mình sẽ bổ sung ngay

Cảm ơn !

[fbchicken]

Code của bạn không có cấu trúc và căn lề cũng tệ nên khó nhìn quá
Mình xin phép chỉnh lại 1 số chỗ:

#include <stdio.h>#include <math.h> int nguyento(int n){    int i, sqrt_n = 0.1 + sqrt(n);  /* Lưu lại cho đỡ phải tính nhiều lần. +0.1 cho chắc ăn vì convert số thực - số nguyên có thể phát sinh vấn đề */    if (n < 2) return 0;    for (i=2; i <= sqrt_n; ++i)        if (0 == n % i) return 0;    return 1;} int main(){    int n, soluong, i=0, k=0, ntlonnhat=0, doronglonnhat=0;    char format[10] = "%2d";     printf("Nhap n : ");    scanf("%d", &n);     printf("Nhap so luong so nguyen to trong 1 dong : ");    scanf("%d", &soluong);     for (i = 2; i<=n; i++)                  /* Tìm ra số nguyên tố lớn nhất trong đoạn [1;n] */        if (nguyento(i)) ntlonnhat = i;     /* i tăng dần nên không cần kiểm tra ntlonnhat > i */    for (doronglonnhat = 1; ntlonnhat >= 10; ntlonnhat /= 10) ++doronglonnhat;    format[1] = '1' + doronglonnhat;        /* chỉ đúng khi doronglonnhat <= 8, chắc vậy là đủ */     for (i = 2; i<=n; i++)                  /* In ra các số nguyên tố với độ rộng thỏa mãn */    {        if (!nguyento(i)) continue;        printf(format, i);        if (++k % soluong == 0) printf("\n");    }     return 0;}

[jetmoon]

#include <stdio.h>
#include <math.h>

int nguyento(int n)
{
    int i, sqrt_n = 0.1 + sqrt(n);  /* Lưu lại cho đỡ phải tính nhiều lần. +0.1 cho chắc ăn vì convert số thực - số nguyên có thể phát sinh vấn đề */
    if (n < 2) return 0;
    for (i=2; i <= sqrt_n; ++i)
        if (0 == n % i) return 0;
    return 1;
}

Mình nghĩ chỗ này

int i, sqrt_n = 0.1 + sqrt(n)

sqrt(n) + 0.1 luôn là kiểu float, mà gán sqrt_n là kiểu int = nó.

[VoTichSu]

Khi tìm số lớn nhất trong một dãy số có thứ tự, ta tìm ngược từ đuôi. Số đàu tiên tìm được là số lớn nhất

    for (i = n; i<=2; i--)                  /* Tìm ra số nguyên tố lớn nhất trong đoạn [1;n] */        if (nguyento(i)) { ntlonnhat = i; break; }     /* i đầu tiên cũng là lớn nhất */

@piavg: cho biết sai ra sao? Kết quả ra sao và nếu đúng thì phải ra sao?

[meterpreter]

@jetmoon: chỗ bạn bảo sai thực ra không sai, vế phải là float sẽ bị ép kiểu ko tường mình sang kiểu nguyên, nghĩa là kiểu của giá trị biểu thức ở về phải phải bị ép kiểu về kiểu của biến ở về trái, cái này nằm trong chuẩn của C,C++ nên ko có gì ngạc nhiên, mà g/s bạn khai báo float sqrt_n = 0.1 + sqrt(n) thì tý nữa xuống vòng for bạn lại phải ép kiểu sqrt_n về int để so sánh với i nên khai báo như trên thì đỡ đi một n lần ép kiểu từ thực sang nguyên và chắc chắn tối ưu hơn.

Tìm số ngto lớn nhất thì làm như VoTichSu sẽ tối ưu hơn.

[piavg]

@piavg: cho biết sai ra sao? Kết quả ra sao và nếu đúng thì phải ra sao?

Khi mình cho chạy cái code của mình thì hiện ra một hàng 10 số 1 cứ chạy liên tục không dừng thôi. Mà code trên mình copy nguyên từ editor của mình vào nên nếu bạn copy y nguyên cái đó vào editor của bạn có lẽ là compile dc ngay, mình thì mình đang muốn hỏi tại sao nó sai mà

Cho mình hỏi một số chỗ mình chưa hiểu (mình viết luôn ở code):

Code của bạn không có cấu trúc và căn lề cũng tệ nên khó nhìn quá
Mình xin phép chỉnh lại 1 số chỗ:

#include <stdio.h>#include <math.h> int nguyento(int n){    int i, sqrt_n = 0.1 + sqrt(n);  /* Lưu lại cho đỡ phải tính nhiều lần. +0.1 cho chắc ăn vì convert số thực - số nguyên có thể phát sinh vấn đề */    if (n < 2) return 0;    for (i=2; i <= sqrt_n; ++i) ([COLOR="Red"]Chỗ này có thể là i++ ko, nếu có thể thì ++i sẽ khác gì[/COLOR])        if (0 == n % i) return 0;    return 1;} int main(){    int n, soluong, i=0, k=0, ntlonnhat=0, doronglonnhat=0;    char format[10] = "%2d"; ([COLOR="Red"]biên char này làm công việc gì[/COLOR])     printf("Nhap n : ");    scanf("%d", &n);     printf("Nhap so luong so nguyen to trong 1 dong : ");    scanf("%d", &soluong);     for (i = 2; i<=n; i++)                  /* Tìm ra số nguyên tố lớn nhất trong đoạn [1;n] */        if (nguyento(i)) ntlonnhat = i;     /* i tăng dần nên không cần kiểm tra ntlonnhat > i */    for (doronglonnhat = 1; ntlonnhat >= 10; ntlonnhat /= 10) ++doronglonnhat;    format[1] = '1' + doronglonnhat; ([COLOR="Red"]mình cũng chưa hiểu chỗ này[/COLOR])     /* chỉ đúng khi doronglonnhat <= 8, chắc vậy là đủ */     for (i = 2; i<=n; i++)                  /* In ra các số nguyên tố với độ rộng thỏa mãn */    {        if (!nguyento(i)) continue; ([COLOR="Red"]sao lại có dấu ! ở trước nguyento(i), và lệnh continue để làm gì[/COLOR])        printf(format, i);        if (++k % soluong == 0) printf("\n");    }     return 0;}

Cảm ơn bạn! (À cho mình hỏi luôn làm sao add code để nó hiện màu như trong editor như của bạn vậy?)

[fbchicken]

Cho mình hỏi một số chỗ mình chưa hiểu (mình viết luôn ở code):



Cảm ơn bạn! (À cho mình hỏi luôn làm sao add code để nó hiện màu như trong editor như của bạn vậy?)

1. Để code có màu thì bạn dùng thẻ code như bình thường, xong thêm viết thêm =C hoặc =C++ vào ([ CODE=C ] , không có dấu cách trong ngoặc vuông)
2. Tìm số nguyên tố lớn nhất thì for ngược lại như VoTichSu nói là chuẩn rồi. Lúc đó mình sửa luôn trên code của bạn nên chưa để ý tối ưu đoạn đó.
3. char format[10]="%2d": Bạn có để ý mình dùng printf(format, i) không? Nếu format không bị thay đổi thì sẽ là tương đương printf("%2d", i). Nhưng lệnh format[1] = '1' + doronglonnhat đã chỉnh cái số 2 thành số tương ứng với độ rộng lớn nhất + 1. Ví dụ doronglonnhat là 3 thì printf(format, i) sẽ tương đương với printf("%4d", i). Vì '1' + 3 = '4'
4. Lệnh continue sẽ nhảy đến thực hiện tiếp lần lặp tiếp theo. Dấu ! là NOT. Tức là nếu i không phải số nguyên tố thì sẽ bỏ qua không thực hiện 2 dòng code ở bên dưới. Viết:

    for (i = 2; i<=n; i++)                  /* In ra các số nguyên tố với độ rộng thỏa mãn */    {        if (!nguyento(i)) continue;        printf(format, i);        if (++k % soluong == 0) printf("\n");    }

tương đương với

    for (i = 2; i<=n; i++)                  /* In ra các số nguyên tố với độ rộng thỏa mãn */    {        if (nguyento(i)) {                printf(format, i);                if (++k % soluong == 0) printf("\n");        }    }

nhưng với cá nhân mình thì cách viết continue dễ nhìn hơn vì 2 lý do:
- 1: Mình nhìn là biết ngay nó sẽ nhảy đến lần lặp kế tiếp, không thực hiện gì khác trong lần lặp đó. Với cách sau, nếu code dài mình còn phải cuộn xuống kiểm tra xem bên dưới block của if có gì nữa không.
- 2: Mỗi block con đều phải căn lề vào trong 1 tab. Mà khi quá nhiều block lồng nhau, lùi vào sâu quá sẽ khó nhìn. Nên mình hạn chế block con khi có thể.

---------------
5. Code của bạn bị lặp vô hạn vì trong vòng lặp for i để in ra, bạn lại thay đổi chính biến i. Sửa lại bằng cách gán 1 biến i2 = i rồi tính toán trên biến i2 là được. (mới xem mỗi chỗ đó, còn có lỗi khác không thì ko rõ )

[piavg]

1. Để code có màu thì bạn dùng thẻ code như bình thường, xong thêm viết thêm =C hoặc =C++ vào ([ CODE=C ] , không có dấu cách trong ngoặc vuông)
2. Tìm số nguyên tố lớn nhất thì for ngược lại như VoTichSu nói là chuẩn rồi. Lúc đó mình sửa luôn trên code của bạn nên chưa để ý tối ưu đoạn đó.
3. char format[10]="%2d": Bạn có để ý mình dùng printf(format, i) không? Nếu format không bị thay đổi thì sẽ là tương đương printf("%2d", i). Nhưng lệnh format[1] = '1' + doronglonnhat đã chỉnh cái số 2 thành số tương ứng với độ rộng lớn nhất + 1. Ví dụ doronglonnhat là 3 thì printf(format, i) sẽ tương đương với printf("%4d", i). Vì '1' + 3 = '4'
4. Lệnh continue sẽ nhảy đến thực hiện tiếp lần lặp tiếp theo. Dấu ! là NOT. Tức là nếu i không phải số nguyên tố thì sẽ bỏ qua không thực hiện 2 dòng code ở bên dưới. Viết:

    for (i = 2; i<=n; i++)                  /* In ra các số nguyên tố với độ rộng thỏa mãn */    {        if (!nguyento(i)) continue;        printf(format, i);        if (++k % soluong == 0) printf("\n");    }

tương đương với

    for (i = 2; i<=n; i++)                  /* In ra các số nguyên tố với độ rộng thỏa mãn */    {        if (nguyento(i)) {                printf(format, i);                if (++k % soluong == 0) printf("\n");        }    }

nhưng với cá nhân mình thì cách viết continue dễ nhìn hơn vì 2 lý do:
- 1: Mình nhìn là biết ngay nó sẽ nhảy đến lần lặp kế tiếp, không thực hiện gì khác trong lần lặp đó. Với cách sau, nếu code dài mình còn phải cuộn xuống kiểm tra xem bên dưới block của if có gì nữa không.
- 2: Mỗi block con đều phải căn lề vào trong 1 tab. Mà khi quá nhiều block lồng nhau, lùi vào sâu quá sẽ khó nhìn. Nên mình hạn chế block con khi có thể.

---------------
5. Code của bạn bị lặp vô hạn vì trong vòng lặp for i để in ra, bạn lại thay đổi chính biến i. Sửa lại bằng cách gán 1 biến i2 = i rồi tính toán trên biến i2 là được. (mới xem mỗi chỗ đó, còn có lỗi khác không thì ko rõ )

Đúng rồi bạn ạ, trước vòng lặp i đặt lại i2=i rồi cho thay đổi giá trị của i2 là ra kết quả. Cảm ơn bạn nhé

[tuanvm90]

code nên viết có tổ chức chút nhé.linh tinh kinh.
fbchicken viết đc roài.