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 Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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

 
Samsung Galaxy get exclusive apps for the Olympics

Samsung Galaxy get exclusive apps for the Olympics

Samsung has teamed-up with Visit Britain to launch “The Best of Britain” app that will be available exclusively on Samsung Galaxy devices.

Hướng dẫn Colorbox Pop-ups cho Drupal Images và Videos

Hướng dẫn Colorbox Pop-ups cho Drupal Images và Videos

A lot of sites like to show media inside pop-ups. Using pop-ups can make it easier for visitors to quicky browse through multiple images or videos.

Mozilla sẽ giới thiệu điện thoại đầu tiên tại MWC 2012?

Mozilla sẽ giới thiệu điện thoại đầu tiên tại MWC 2012?

Mozilla đã hợp tác với LG nhằm cho ra mắt thiết bị di động đầu tiên của họ tại MWC 2012, một nguồn tin thân cận đã xác nhận với trang ExtremeTech.

Wordpress Freelancer

 

Wordpress Freelancer