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
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;
}
Đã thử 4 vào và chương trình trên xác nhận rằng: 4 là số nguyên tố
Đây là bài của e , mọi ng có thể xem thử ( sai thì sửa em với)
fb của em : fb.com/sstrrikerr
kí tên Thiên Bá CSGO =)))
______________________________________________________
#include
int main()
{
int n, i;
scanf( “%d”, &n);
if( i== 1,2)
{
printf( “%d la so nt”, n);
}
else
{
for( i= 2; i< n; i++)
{
if( n%i == 0)
{
printf( "khong phai la so nt");
break;
}
}
printf( "%d la so nt", n);
}
return 0;
}