Số nguyên tố có giá trị không lớn hơn N

Bạn nào giải thích giúp mình bài này với ạ?

#include "pch.h"
#include <iostream>

using namespace std;

int main()
{
    int N;
    cout << "\nnhap gia tri N: ";
    cin >> N;
    cout << "\ncac so nguyen to co gia tri khong lon hon N: ";
    for (int i = 2; i < N; i++)
    {
        for (int j = 2; j*j <= i; j++)
        {
            if (i % j == 0)
                break;
            else if (j + 1 > sqrt(i)) {
                cout << i << endl;
            }
        }
    }
}

Ôn lại định nghĩa:

  • Hợp số là tích của hai số tự nhiên lớn hơn 1 (n = a * b).
  • Số nguyên tố là số có đúng hai ước 1 và chính nó.

Số 1 đứng ngoài cả hai tập và nó là một phần tử đơn vị (bạn nào học Số học ở ĐH rồi sẽ hiểu). Ta nói rằng hợp số và số nguyên tố là một phân hoạch của N* \ {1}.

Khi viết n = a*b thì (a, b) là một cặp :smiley: và luôn có a <= sqrt(n) <= b, vì nếu a < b < sqrt(n) thì ab < n, còn b > a > sqrt(n) thì ab > n. Vậy chạy từ 2 đến sqrt(n) là xong.

Thuật toán như sau:

: Input: n: uinteger
: assert n >= 2: return false;
for i = 2 to trunc(sqrt(n)) do if n MOD i = 0 return false;
return true;

Vậy nếu j <= sqrt(n) thì j*j <= n thôi.

3 Likes

biến j đó là gi ạ :smiley:

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?