Số nguyên tố là gì ? Hàm tìm số nguyên tố

Tìm Số nguyên tố là một bài toán kinh điển trong lập trình. Vậy số nguyên tố là gì ?  Thường số nguyên tố sẽ được định nghĩa như sau; số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước số là 1 và chính nó.

Có nhiều cách tìm số nguyên tố. Chúng ta cùng làm rõ vấn đề này với oktot nhé.

Ví dụ 1: Viết chương trình kiểm tra số nguyên nhập vào từ bàn phím có phải là số nguyên tố hay không?

Thuật toán:

Code C/C++

#include <stdio.h>
#include <conio.h>

void main()
{
	int n, dem=0;
	/*Nhập vào giá trị nguyên lớn hơn 2 cần kiểm tra có phải là số nguyên tố*/

	do
	{
		printf("\n Nhap vao so nguyen N: ");
		scanf("%d", &n);
	}while(n<=2);
	for (int i=1; i<=n; i++)
	{
		if (n%i==0)
		{
			dem ++;
		}
	}
	if (dem==2)
	{
		printf("Day la so nguyen to");
	}
	else
	{
		printf("Day khong phai la so nguyen to");
	}
	getch();
}

Ví dụ 2: Viết chương trình tìm số nguyên tố nhỏ hơn N

Code C/C++

#include <stdio.h>
#include <conio.h>

void main()
{
  int n, i, j;

  printf("\nNhap gia tri N : ");
  scanf("%d", &n);
  printf("\nCac so nguyen to nho hon n la : ");
  for (i=2; i<n; i++)
  {
    for (j=2; j<i; j++)
      if (i%j == 0)
        break;
    if (j == i)
      printf("%d ", i);
  }

  getch();
}

Ví dụ 3: Viết Hàm tìm số nguyên tố

1. Input: 01 số nguyên dương n (kiểu int)
2. Output: có hoặc không, đúng hoặc sai, true hoặc false => kiểu trả về là int (1: đúng, 0: sai)
3. Thuật toán:

   Kiểm tra trong khoảng từ 2 đến n -1. nếu n chia hết một số bất kỳ nào đó thì h không phải là số nguyên tố, ngược lại n là số nguyên tố.

Code C/C++

Cách 1:

// hàm kiểm tra xem có phải là số nguyên tố hay không
int KTSoNT(int n)
{
	if (a<=1)
		return 0;
	for(int i = 2 ; i<n ; i++)
		if(n%i==0)
			return 0;    // không phải SNT trả về 0
	return 1;           // là SNT trả về 1
}

Cách 2:

bool KTSoNT(int n)
{
	if (n < 2)
		return false;
	for (int i = 2; i<= n/2; ++i)
		if (n % i == 0)
			return false;
	return true;
}

Xem thêm Nhập xuất mảng một chiều