Bài toán kinh điển trong lập trình

Tổng hợp những bài toán trong lập trình, ngẫu nhiên từ cơ bản đến nâng cao.

Kiểm tra N có phải là số nguyên tố hay không ? Kiểm tra N có phải là số nguyên tố hay không ? Kiểm tra N có phải là số nguyên tố hay không ? Kiểm tra N có phải là số nguyên tố hay không ? Kiểm tra N có phải là số nguyên tố hay không ? 3.3/5 (163 reviews)

Kiểm tra N có phải là số nguyên tố hay không ?

Đã đăng 2017-07-08 23:19:10 bởi Kteam
7 bình luận 42189 lượt xem
Kiểm tra N có phải là số nguyên tố hay không ? 3.3 /5 stars (10 reviews)
 

Mục tiêu

Làm quen cách viết các chương trình đơn giản, cách sử dụng:

Yêu cầu bài toán

Viết chương trình nhập số nguyên dương n. Kiểm tra n có phải là số nguyên tố hay không?

Ví dụ:

  • Input: 3
  • Output: 3 là số nguyên tố

Hướng dẫn

Định nghĩa

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, ... là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất. 

Cũng như tính chất của số nguyên dương, chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không thể tìm thấy số nguyên tố lớn nhất.

Thuật toán

Dựa vào định nghĩa của số nguyên tố chúng ta sẽ có cách giải như sau:

  • Bước 1: Nhập vào n
  • Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố
  • Bước 3: Lặp từ 2 tới (n-1), nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.

Lưu ý: Vẫn còn rất nhiều cách khác nhưng chung quy lại vẫn phải bám vào định nghĩa số nguyên tố là gì. Ví dụ trong vòng lặp điểm dừng sẽ là (n/2) thay vì (n-1) vì theo lý thuyết thì một số không bao giờ chia hết cho số lớn hơn một nửa của nó. Ví dụ số 9 thì số một nửa của nó là số (9 : 2 = 4), như vậy ta chỉ cần kiểm tra các số từ 2,3,4 mà thôi, còn các số 5,6,7,8 chắc chẵn 9 sẽ không chia hết.

 

Kteam khuyến khích các bạn tự phân tích đề bài > tự giải bài toán > debug để kiểm tra kết quả và fix lỗi trong quá trình giải. Sau đó, bạn có thể tham khảo source code mẫu để hoàn chỉnh bài tập. 

Để được hỗ trợ tốt nhất, bạn có thể đặt câu hỏi ở phần BÌNH LUẬN bên dưới bài viết hoặc ở mục Hỏi & Đáp.

 

Source code tham khảo

// Viet chuong trinh nhap so nguyen duong n.Kiem tra n co phai la so nguyen to hay khong?

=============================================================


#include <iostream>
using namespace std;

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

void main()
{
	unsigned int n;
	cout<<"Nhap vao so nguyen duong n: ";
	cin>>n;
	if(KTSNT(n)==true)
		cout<< n << " la so nguyen to!";
	else
		cout<< n <<" khong la so nguyen to!";
	cout<<endl;
}


Kết luận

Bạn có thể củng cố kiến thức C++ từ khóa LẬP TRÌNH C++ CƠ BẢN.

Hoặc tìm hiểu thêm các bài tập khác trong khóa Bài toán kinh điển trong lập trình

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của bạn để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

Chia sẻ:
Thảo luận Hỏi và đáp Báo lỗi bài viết
Hủy bỏ   hoặc  
Kiểm tra N có phải là số nguyên tố hay không ?
Lolipedia 2018-11-07 22:11:22
#include "pch.h"
#include <iostream>
using namespace std;

int checknumber(int n)
{
	int dem = 0;
	for (int a = 2; a < n; a++)
	{
		if (n%a == 0 && n != 2)
		{
			dem++;
		}
	}
	return dem;
}
int main()
{
	int N;
	cout << "Enter a number:";
	cin >> N;
	int a = checknumber(N);
	if (a == 0) cout << "N la so nguyen to." << endl;
	else cout << "N khong phai so nguyen to" << endl;
	return 0;
}

của mình thì thế này.

0 bình chọn
Reply
Kiểm tra N có phải là số nguyên tố hay không ?
Lê Hoàng Khang 2018-09-12 11:36:24

cho em hỏi : vì sao cái vòng lặp for lại có cái điều kiện i<=x/2 vậy ạ em không hiểu lắm 

0 bình chọn
Reply
View all 1 comments
Kteam - Howkteam Free Education
K9 2018-09-13 14:21:06
thuật toán rút ngắn số lần phải duyệt. vì số chẵn chắc chắn có ước là 2. =&gt; duyệt tới 1/2 là ok rồi. từ đó mở rộng hơn là duyệt tới căn bậc 2 là đã biết thằng đó có phải số nguyên tố hay k
0 bình chọn
Reply
Kiểm tra N có phải là số nguyên tố hay không ?
tvc12591 2018-05-01 11:00:21

Python

def songuyento(_n):
    if _n < 0:
        print('Số bạn nhập không chính xác')
    elif _n == 1 or _n == 2:
        print('Đây là số nguyên tố')
    else:
        _dem = 0
        for _i in range(1,_n//2):
            if _n % _i == 0:
                _dem = _dem + 1
        if _dem == 0:
            print('Đây là số nguyên tố')
        else:
            print('Đây không là số nguyên tố')
    return

 

0 bình chọn
Reply
Kiểm tra N có phải là số nguyên tố hay không ?
d3c0d3d 2017-07-11 21:38:15
#include ;
using namespace std;

int main()
{
	int n;
	cout << "Nhap so tu nhien can kiem tra: ";
	cin >> n;
	int nKiemTra = 2;
	while (nKiemTra < n)
	{
		int nSoDu = n % nKiemTra;
		if (nSoDu == 0)
		{
			cout << n << " khong la so nguyen to." << endl;
			break;
		}
		else
		{
			nKiemTra += 1;
			if (nKiemTra == n)
			{
				cout << n << " la so nguyen to."<< endl;
			}
		}
	}

	system("pause");
	return 0;
}

Em thì làm thế này.

1 bình chọn
Reply
Kiểm tra N có phải là số nguyên tố hay không ?
minhtuancnttk39 2017-07-10 11:39:05

Bài đó với độ phức tạp như thế thì nếu mình nhập vào 1 số tự nhiên 10^12 thì chương trình sẽ bị Time Limit.
- Vì độ phức tạp của thuật toán trên là O(1/2 * N): trong đó 1/2 là const nên được xem là O(N).

- Vì thế để cải tiến, mình chỉ sử dụng thuật với đpt là O(sqrt(N)) như sau:

bool isPrime1(long long n) {
    if(n < 2) return false;
    int _n = (int)sqrt(n);
    for (int i = 2; i <= _n; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

// hoặc

bool isPrime2(long long n) {
    if(n < 2) return false;
    for (ll i = 2; i*i <= n; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

Thân ái.

1 bình chọn
Reply
View all 1 comments
Kteam - Howkteam Free Education
K9 2017-07-10 21:11:46
mọi người xem bình luận để có đáp án cool hơn
0 bình chọn
Reply
Hủy bỏ   hoặc  
Hủy bỏ   hoặc  

Chiến dịch

Kteam - Howkteam Free Education