Thuật Toán về kiếm tra tính chất nguyên tố của một số cài đặt bằng C/C++

Thuật Toán về kiếm tra tính chất nguyên tố của một số cài đặt bằng C/C++

Số nguyên tố là số tự nhiên lớn hơn 1 chia hết cho 1 và chính nó.

* Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho một số m nằm trong khoảng từ 2 đến n-1 hay không. Nếu n chia hết cho m thì n không là số nguyên tố, ngược lại n là số nguyên tố.
* Ngoài ra do tính chất của Hợp số thì nó chắc chắn có ước số không vượt quá \sqrt n, vì vậy ta chỉ cần kiểm tra từ 2 đến \sqrt n.

* Chúng ta cũng có thể bỏ qua việc kiểm tra các trường hợp là bội số của 2 và 3 bằng cách kiểm tra các số lẻ. Các số lẻ này có dạng 6k-1 và 6k+1 và k = 0, 1, 2, 3...

Chương trình cài đặt

#include<iostream>

#include<conio.h>

using namespace std;

bool isPrime(int n){

  if(n == 2 || n== 3) return true;

  if(n == 1 || n%2 == 0 || n%3 == 0) return false;

  int k = -1;

  do{

   k+=6;

   if(n%k == 0 || n%(k+2)==0) break;

  }while(k*k < n);// k < sqrt(n);

  return k*k>n;// return k > sqrt(n).

}

int main(){

 int n;

 cout<<"Input number:";

 cin>>n;

 if(isPrime(n)){

  cout<<n<<" is prime";

 }else{

  cout<<n<<" is not prime";

 }

 _getch();

 return 0;

}
Bạn thấy bài viết này như thế nào?: 
Average: 10 (2 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Firefox 9.0 Beta 4 lướt web nhanh và mượt hơn

Firefox 9.0 Beta 4 lướt web nhanh và mượt hơn

Nhịp điệu mỗi tuần ra một bản Beta mới của Firefox vẫn được Mozilla duy trì. Tương tự những lần trước, Firefox 9.0 Beta 4 cũng cải thiện về tốc độ xử lý JavaScript và giảm chiếm dụng bộ nhớ đôi chút.

Hướng dẫn rebuild Drupal 7 administration menu

Hướng dẫn rebuild Drupal 7 administration menu

Sometimes it happens your Drupal 7 administration menu gets scrambled. This may be caused by some nasty modules, or like in my case it was inherited from MySQL crash in Drupal 6 version of a site.

Samsung Conquer 4G Review

Samsung Conquer 4G Review

Though to be a budget 4G devices, the Samsung Conquer 4G is very elegant and stylish. I was surprised at how well put together this phone is. The manufacturers seemed to have put a lot of attention to detail when making this gadget.

Công ty diệt chuột T&C

 

Diet con trung