[C++] [Lỗi] bài tập xác định Số nguyên tố!

[lytieulong_269]

Mình mới suy nghĩ ra được cách tìm "Số nguyên tố" nhanh không phải học thuộc bài code máy móc như cách trước đây là phải gọi biến "dem"!! Mình làm như sau:

- Cho vòng "for" chạy từ "i đến căn(n)" nếu phát hiện có giá trị i nào đó..... bị n chia hết thì ngừng vòng lặp ngay ( break; ) và thông báo "n không là số nguyên tố!" . Tất nhiên là cách này tiết kiệm được chút thời gian so với cách gọi biến "dem" (vòng for phải chạy từ 1->n và mất công hơn nếu i=2 mà n đã chia hết cho i rồi......... mà for chứ chạy và "dem" tới n phải ko?.
- Tuy nhiên, tất cả không phải dễ dàng như mình đã nghĩ! Ở TH nếu "n là số nguyên tố" thì sao? Các bạn suy nghĩ trước đi rồi đọc sau nhé!

uk, chỉ còn cách duy nhất là cho điều kiện "n là số nguyên tố vào vòng lặp for" và gán cho nó thêm một điều kiện nữa! Xong, có vẻ như đã hoàn hảo rồi! Nhưng mọi việc lại khó khăn hơn khi các giá trị "9, 15, 25, 35" có là số nguyên tố hay không thì chương trình lại không thông báo, các giá trị khác vẫn hoạt động bình thường. Lỗi ở đâu thì mình ko tìm ra được. Đoạn code của mình đây, mong các bạn giúp mình hoàn thành ý tưởng này với!!

Các bạn chú ý chỉ nhập các số >3 thôi! Các trường hợp <=3 mình sẽ xét riêng ngoài vòng for!

#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{
int i, n;
scanf("%d",&n);
for(i=2; i<=sqrt(n); i++)
{
if(n%i == 0)
{
printf("%d khong la so nguyen to ", n);
break;
}
if(i = int(sqrt(n)))
{
if(n%i != 0)
printf("%d la so nguyen to ",n);
}
}
getch();
}

[10520058]

if(i = int(sqrt(n)))
{
if(n%i != 0)
printf("%d la so nguyen to ",n);
}

cái này làm gì vậy bạn bỏ cho khỏe thay bằng printf ("%d la so nguyen to",n) là được mà không biết đúng không nữa

[lytieulong_269]

Bạn nói hay quá! Thử đi nha... haha được n dòng "n là số nguyên tố" đó bạn!

[08520604]

Cho hỏi xíu , ý bạn ở chỗ này là sao vậy

if(i = int(sqrt(n)))
{

?

Là phép so sánh hay là phép gán ,nếu là gán thì hình như ở trên vòng for đã gán rồi mà ?

[11520145]

- Tuy nhiên, tất cả không phải dễ dàng như mình đã nghĩ! Ở TH nếu "n là số nguyên tố" thì sao? Các bạn suy nghĩ trước đi rồi đọc sau nhé!

uk, chỉ còn cách duy nhất là cho điều kiện "n là số nguyên tố vào vòng lặp for" và gán cho nó thêm một điều kiện nữa! Xong, có vẻ như đã hoàn hảo rồi! Nhưng mọi việc lại khó khăn hơn khi các giá trị "9, 15, 25, 35" có là số nguyên tố hay không thì chương trình lại không thông báo, các giá trị khác vẫn hoạt động bình thường. Lỗi ở đâu thì mình ko tìm ra được. Đoạn code của mình đây, mong các bạn giúp mình hoàn thành ý tưởng này với!!

ý anh cho thêm điều kiện là sao ah

[lytieulong_269]

Mình viết như vậy với dụng ý là khi điều kiện thứ nhất chưa thực thi (nghĩa là chưa thoát khỏi for) cũng là lúc i đã chạy đến giá trị áp chót = int(sqrt(n). Ta sử dụng câu lệnh thứ 2 để kiểm tra lần cuối và đưa ra kết luận bạn ạ!

[10520058]

#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{
int i, n;
scanf("%d",&n);
while(n<2)
{
scanf("%d",&n);
};
for(i=2; i<n; i++)
{
if(n%i == 0)
{
printf("%d khong la so nguyen to ", n);
break;
}
printf ("%d la so gnuyen to",n);
}
getch();
}

[lytieulong_269]

Trời! Già quá lẩm cẩm mất.... i = int(sqrt(n) sửa lại "i == sqrt(n)" Vậy mà nhìn suốt buổi ko ra mới đau.

[11520145]

- Tuy nhiên, tất cả không phải dễ dàng như mình đã nghĩ! Ở TH nếu "n là số nguyên tố" thì sao?

uk, chỉ còn cách duy nhất là cho điều kiện "n là số nguyên tố vào vòng lặp for"

Các bạn chú ý chỉ nhập các số >3 thôi! Các trường hợp <=3 mình sẽ xét riêng ngoài vòng for!


if(n%i != 0)
printf("%d la so nguyen to ",n);
}

Nếu trường hợp N cũng là số nguyên tố thì không cần phải xét n đâu - cứ chạy tới sqrt(n) bình thường nếu không chia hết cho số nào thì n cũng chính là số nguyên tố rôi nên bỏ đoạn code cuối cùng đi cũng không sao. Còn nhập số <=3 thì mình đã chạy từ 2 rồi còn gì, có nghĩa là cũng đã xét luôn số 2 và nó là số nguyên tố luôn ( 0 và 1 không phải là số nguyên tố )

http://vi.wikipedia.org/wiki/S%E1%BB%91_nguy%C3%AAn_t%E1%BB%91

[11520145]

Cái này xin nói ngoài lề nha :P ( không phải spam đâu T.T )
Số nguyên tố lớn nhất

Giả thiết 1: Không có số nguyên dương X nào là số nguyên tố lớn nhất, nghĩa là không tồn tại số mà các số lớn hơn nó Y > X sẽ buộc phải chia hết cho các số nguyên nhỏ hơn hoặc bằng X
Giả thiết 2: số vô cùng lớn ∞ không thể xác định là số nguyên tố hay hợp số
Giả thiết 3: Lực lượng của tập hợp số nguyên tố là vô hạn đếm được
Với 3 giả thiết trên thì việc xác định số nguyên tố lớn nhất là không thể được; tuy nhiên, với khả năng tính toán của máy tính, người ta có thể tính ra được số nguyên tố (số nguyên chắc chắn là số nguyên tố) lớn nhất tính được đến tháng 9 năm 2008 là số nguyên tố Mersenne thứ 45 (hay 46 nếu tính cả số 1) với 12,978,189 chữ số:
243,112,609 − 1.. (http://vi.wikipedia.org/wiki/S%E1%BB...AAn_t%E1%BB%91 )
Và thế hệ tiếp theo là chúng ta đây - hãy tìm ra số nguyên tố lớn hơn số thứ 45 đó đi nào :P

[lytieulong_269]

Bạn Huy nói vậy mình nghĩ là chưa đúng!
"cứ chạy tới sqrt(n) bình thường nếu không chia hết cho số nào thì n cũng chính là số nguyên tố rôi nên bỏ đoạn code cuối cùng đi cũng không sao. Còn nhập số <=3 thì mình đã chạy từ 2 rồi còn gì, có nghĩa là cũng đã xét luôn số 2 và nó là số nguyên tố luôn ( 0 và 1 không phải là số nguyên tố )".
Giả thiết của mình n>3 còn điều kiện i chạy từ 2 để làm gì thì bạn nên suy nghĩ lại nhé!
Cho hỏi, nếu bỏ đoạn code sau thì bạn có thể xuất ra dòng thông báo "n là số nguyên tố" hay không? Nếu được bạn hãy chưa đoạn code của bạn đây cho mình test thử.

[09520019]

Hok hiểu bạn Đức Huy đang khoe cái gì nữa ? Tài tính toán số to béo chăng ? Cho mình hỏi bạn đọc tài liệu wiki đó trong bao lâu ? Vì số nguyên tố Mersenne và số nguyên tố là 2 khái niệm khác nhau nhé, số nguyên tố thứ 45 nhỏ hơn 1000 là điều chắc chắn
Bạn Quốc Huy thì lại "có vấn đề" về coding. Bạn code mình chắc chắn bạn chưa test. Bạn thử nhập số 15 rồi cho mình biết kết quả nhé. Chưa kể bạn cho i = 2 đến n, trong khi thực tế chỉ cần chạy tới căn n là đủ.

Cách code kiểu này các bạn thường thích "tiết kiệm" mà mình thấy tiết kiệm trong TH này là không cần thiết. Có 2 cách tiếp cận vấn đề:

+ Cách tránh gọi hàm, chỉ dùng khi bạn chưa học chương trình con bao giờ (thầy bắt code vậy):

[B][COLOR="#FF0000"]int ngto = 1;[/COLOR][/B]
if (n < 2) ngto = 0; else
for(i=2; i<= sqrt(n); i++)
    if(n%i == 0)
    {
        [B][COLOR="#FF0000"]ngto = 0;[/COLOR][/B]
        break;
    }
if (ngto == 1) printf("Day la so nguyen to"); else printf("Day khong phai la so nguyen to");

+Cách thứ 2 là gọi hàm, mình luôn luôn dùng cách này vì tính rõ ràng của thuật toán, và gọi 1 hàm thì ko tốn bao nhiêu nanosecond đâu mấy bạn. Tiết kiệm quá không có tốt. Ngoài ra thay vì dùng sqrt có nhược điểm là phải xử lý số thực, mình ko ưa số thực lắm nên thay vì i <= sqrt(n) đổi thành i * i <= n.

int IsPrime(int n)
{
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3;i * i <= n;i += 2)
        if (n % i == 0) return 0;
    return 1;
}

Is that simple ?
Nếu bạn thích chương trình chạy nhanh hơn thông qua việc không gọi hàm, thì bạn sửa
int IsPrime(int n) thành inline int IsPrime(int n)

[07520004]

+Cách thứ 2 là gọi hàm, mình luôn luôn dùng cách này vì tính rõ ràng của thuật toán, và gọi 1 hàm thì ko tốn bao nhiêu nanosecond đâu mấy bạn. Tiết kiệm quá không có tốt. Ngoài ra thay vì dùng sqrt có nhược điểm là phải xử lý số thực, mình ko ưa số thực lắm nên thay vì i <= sqrt(n) đổi thành i * i <= n.

giữa việc tính sqrt(n) một lần với việc tính sqrt(n) lần số i*i chưa chắc cái nào nhanh hơn nha. Ở đây mình chỉ cần phần nguyên của căn bậc hai nên chắc là có cách tính nhanh, nhưng mà thôi cũng không cải thiện được bao nhiêu

Nếu bạn thích chương trình chạy nhanh hơn thông qua việc không gọi hàm, thì bạn sửa
int IsPrime(int n) thành inline int IsPrime(int n)

Với một hàm đơn giản như isprime thì compiler sẽ tự động inline nó, hầu hết các compile bây giờ đều vậy nên chúng ta cũng không cần quan tâm quá tới vụ này.

Tóm cái váy bó cái gọn là viết cái hàm vầy dễ quá mà, có gì hot đâu. Còn tìm số nguyên tố cực lớn thì là một vấn đề khá thú vị hình như kỷ lục bây giờ là vài tỉ chữ số rồi thì phải và cái đó chắc trường ta không có ai chơi đâu =))

[11520145]

Hi - xin lỗi bạn Long vì hiểu nhầm đoạn cuối của bạn và cám ơn anh Châu đã giải thích.