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

 
Nguyễn Siêu Hạnh nhận giải thưởng của Liên Hiệp Quốc

Nguyễn Siêu Hạnh nhận giải thưởng của Liên Hiệp Quốc

Chàng trai 25 tuổi Nguyễn Siêu Hạnh, sinh viên năm cuối khoa Quản trị kinh doanh, Học viện UBI (Bỉ), vừa nhận giải thưởng World Summit Youth Award của Liên Hiệp Quốc vào tháng 11 vừa qua tại Áo.

Ví dụ sử dụng 2 function theme_table() và theme_fieldset() trong Drupal 7

Ví dụ sử dụng 2 function theme_table() và theme_fieldset() trong Drupal 7

In Drupal 7 API there is a chapter dedicated to site theming. All elements of a site, without exclusion, should go through the theming process.

Đến Từ NAG Ryan McKinnon

[Share Preset] Tone Màu Film Cho Ảnh Sexy Đến Từ NAG Ryan McKinnon

Bao gồm 02 preset với tone màu đậm, đặc biệt phù hợp với ảnh nude, sexy….theo tác giả, đây không phải là preset “bấm phát ăn ngay”

Tomdesgin.vn

 

Drupal Services