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

 
Hướng dẫn update cho theme trong Drupal

Hướng dẫn update cho theme trong Drupal

In the example below, we have version 7.x.-1.0 of the Zero Point theme on our site.

Cập nhật hứơng dẫn SEO với 301 Redirect

Cập nhật hứơng dẫn SEO với 301 Redirect

Ắt hẳn khi thực hiện seo từ khóa, bạn sẽ gặp phải trường hợp một URL bạn đã chăm chút để đạt thứ hạng cao trên công cụ tìm kiếm, nhưng giờ URL đó lại bị thay đổi (do cập nhật website, ngôn ngữ mới, trang gốc bị xóa…). Bài viết này sẽ giúp bạn thực hiện điều đó.

Dark web không thể truy cập bằng cách thông thường mà phải sử dụng các phần mềm chuyên biệt

Các dịch vụ trên dark web - hack một trang web với giá 2.000 USD

Tôi cần hack một trang web với giá 2.000 USD", "Đánh sập trang web này với giá 10.000 USD"... là những yêu cầu đăng đầy trên các diễn đàn hacker.

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

 

Diet con trung