Chương trình kiểm tra xem số N có phải là số nguyên tố không?

Yêu cầu:

Viết chương trình kiểm tra xem số N có phải là số nguyên tố không?

Thuật toán:

– Số nguyên tố là số chỉ chia hết cho chính nó và 1.

Ví dụ: 1, 3, 5, 7, 11, 13,… là số nguyên tố

– Nếu (N%i == 0) với mọi i = ( 2 – N/2) thì N là số nguyên tố.

Code:

/************************************************************
* Author: VNCODING
* History 
* 2014/03/17 first create VNCODING
*************************************************************/
#include "stdio.h"
#include "conio.h"

int so_nguyen_to(int N);
void main()
{
    int N;
    int ketqua;
    do
    {
        printf("\n Nhap vao so N = ");
        scanf("%d", &N);
    }
    while(N <= 0);
    if(so_nguyen_to(N))
        printf("\n %d la so nguyen to", N);
    else
        printf("\n %d la khong phai so nguyen to", N);
    getch();
}
// Ham kiem tra so nguyen to
int so_nguyen_to(int N)
{ 
    int i;
    if(N == 1)
        return 1;
    else
    {
        for( i = 2; i < N/2; i++)
        { 
            if(N % i == 0)
                return 0;
        }
        return 1;
    }
}

Kết quả:

Nhap vao so N = 12
12 la khong phai so nguyen to

Nhap vao so N = 17
17 la so nguyen to

2 Comments on Chương trình kiểm tra xem số N có phải là số nguyên tố không?

  1. Có thể dùng sàng Eratosthenes
    #include “stdafx.h”
    #include
    #include

    using namespace std;

    int main()
    {
    int n, temp, dem=0;
    bool isprime[200000];
    cout << "Tim tat ca so nguyen to tu 2 den N\n";
    cout <> n;
    temp = (int)sqrt(n); // Kiem tra lai lan nua
    cout << "Ta co cac so nguyen to: ";
    fill_n(isprime, n, true); // Gia su toan bo deu la so nguyen to
    isprime[1] = false;
    for (int i = 2; i <= temp; i++) // Chi chay den sqrt(n). Nhung so lon hon ko can quan tam
    if (isprime[i] == true)
    for (int k = i + 1; k <= n; k++)
    if (isprime[k] == true && k % i == 0)
    isprime[k] = false;
    for (temp = 2; temp <= n; temp++)
    if (isprime[temp] == true)
    {
    dem++;
    cout << temp << " ";
    }
    cout << endl << "Co tat ca " << dem << " so" << endl;
    return 0;
    }

Leave a Reply

Your email address will not be published.

*