[Wiki] Hàm Kiểm Tra số nguyên tố trong C/C++

[Honey_moon (Thực tế khắc nghiệt)]

Số nguyên tố:

• Số nguyên tố là số tự nhiên chỉ chia hết cho 1 và chính nó. Ngoài ra nó không chia hết cho bất cứ số nào khác. Số 0 và 1 không được coi là số nguyên tố. - Theo wiki

• Số 2 là số nguyên tố chẵn duy nhất.

• Cấu trúc ở dạng C:

int soNguyenTo(int soA)
{
    if (soA < 2)    
        return 0;

    for (int i = 2; i <= sqrt((float)soA); i ++)
    {
        if (soA%i==0)
        {
            return 0;
        }
    }
    return 1;
}

• Định nghĩa : Do người dùng tự tạo. Có thể có nhiều cách để tối ưu.
  Ví dụ : Hãy kiểm tra xem số bạn nhập có phải là 1 số nguyên tố hay không ?

• Code minh hoạ C++

#include <iostream>
using namespace std;
bool soNguyenTo(int);
bool soNguyenTo(int soA) // hàm bool trả về true/false
{
	if (soA < 2) // Nếu số A nhỏ hơn 2
	{
		return false;// trả về false
	}
	else if (soA>2)// Nếu số A lớn hơn 2
	{
		if (soA % 2 == 0)  // Xét xem A có chia hết cho 2 không?
		{
			return false;// Nếu chia hết, return false.
		}
		for (int i = 3; i < sqrt((float)soA); i += 2)  // xét từ 3 đến căn bậc 2 của số A
		{
			if (soA%i == 0)  // nếu A chia hết cho một số nào đó trong đoạn này
			{
				return false;// trả về kết quả sai
			}
		}
	}
	return true;// sau tất cả các chỗ trên, nó mà không sai thì cuối cùng nó đúng :3
}
int main(int argc, char ** argv)
{
	int n; // khai bao so kiem tra la so nguyen
	cout << "Nhap so can kiem tra?!" << endl;
	cin >> n; // nhap vao so nguyen tu ban phim
	if (soNguyenTo(n) == true)
	{
		cout << "So " << n << " la so nguyen to!!!!";
	}
	else
	{
		cout << "So " << n << " khong phai nguyen to!!!!";
	}
	system("pause");
	return 0;
}

• Hình minh họa:

[TTmagic]

góp vui bức hình

[minh_vu_03]

bool soNguyenTo(int soA)
{
	if (soA < 2)
	{
		return false;
	}
	else
	{
		for (int i = 2; i <= sqrt((float)soA); i ++)
		{
			if (soA%i==0)
			{
				return false;
			}
		}
	}
	return true;
}

Rút ngắn lại như trên cho dễ nhìn hơn. Các bác mới học nhìn vô cũng dễ hiểu hơn.

[Honey_moon (Thực tế khắc nghiệt)]

Rút ngắn lại như trên cho dễ nhìn hơn. Các bác mới học nhìn vô cũng dễ hiểu hơn.

đang tính viết từ thô sơ tới tối ưu mà nghĩ lại cái để vậy luôn. kakaka

[yuh (Huy)]

mình luôn dùng cách này vì mình nghĩ nó sẽ chạy nhanh hơn khi chỉ phải xét các số lẻ thay vì phải xét hết liên tiếp
for (i=3->sqrt(n), i+=2

[Honey_moon (Thực tế khắc nghiệt)]

mình luôn dùng cách này vì mình nghĩ nó sẽ chạy nhanh hơn khi chỉ phải xét các số lẻ thay vì phải xét hết liên tiếpfor (i=3->sqrt(n), i+=2

wiki xét thế mà bạn?

[nguyenvanquan7826 (Quân)]

Các bức hình bên trên của thuật toán sàng nguyên tố

[ltd (Lê Trần Đạt)]

Wow, anh còn không biết Làm vài bài ủng hộ đi @nguyenvanquan7826

[yuh (Huy)]

nhớ không lầm là chỉ sàng được n<100

[nguyenvanquan7826 (Quân)]

Tìm 100 thì tìm làm gì bạn
Nó dùng trong các bài toán tìm số nguyên tố trong khoảng từ a->b mà a rất nhỏ, b rất lớn, tức là khoảng cách rất lớn.

[nguyenvanquan7826 (Quân)]

Sắp có anh ợ.

[nguyenvanquan7826 (Quân)]

Vừa lúc sáng viết lại thử cái sàng nguyên tố

[Honey_moon (Thực tế khắc nghiệt)]

Vừa lúc sáng viết lại thử cái

chuẩn men kakakakaka

[SoiLuv (Nguyễn Duy Khánh)]

Đa số e thấy mn toàn dùng cách là xét chia hết cho các số lẻ từ 3 -> sqrt(n).
Và thấy nhiều người bảo là tối ưu nhất
Các SNT trừ 2 và 3 ra để có dạng (6k + 1) hoặc (6k - 1)
Code C++

bool Is_Prime(int n)
{
	if ((n == 2) || (n == 3))
	{
		return true;
	}
	if ((n % 2 == 0) || (n % 3 == 0) || (n < 2))
	{
		return false;
	}
	int i = -1, sqrt_n = sqrt(n);
	do
	{
		i += 6;
		if ((n % i == 0) || (n % (i + 2) == 0))
		{
			break;
		}
	} while (i <= sqrt_n);
	return (i > sqrt_n);
}

Có gì sai sót mong mn chỉ bảo

[Em_Beeng]

Tại sao phải xét từ 2 đến căn bậc hai của số A

[Em_Beeng]

tai sao chạy từ 2- sqrt(A)

[Gio (Gió)]

dễ dàng chứng minh nếu A là hợp số thì sẽ có ít nhất 1 ước #1 <=sqrt(A)

bởi nếu tất cả các ước #1>sqrt(A) thì ước1 * ươc2 … >A

[Em_Beeng]

ukm, thanks

[Lam_Quang_Minh (Lâm Quang Minh)]

Đa số hiện nay người ta sử dung đơn giản ý tưởng như Nguyễn Duy Khánh, đó là ý tưởng bước nhảy 2, 4 so le với nhau, có nhiều cách viết nhưng ý tưởng là vậy

[manhcuong199748 (nguyễn mạnh cường)]

do
	{
		i += 6;
		if ((n % i == 0) || (n % (i + 2) == 0))
		{
			break;
		}
	} while (i <= sqrt_n);
	return (i > sqrt_n);

cái đoạn này ai giải thích trình tự hđ của nó dc k