Code kiểm tra số nguyên tố trong C

Phát biểu bài toán kiểm tra số nguyên tố : Cho 1 số ít nguyên x nhập từ bàn phím. Hãy kiểm tra xem số x có phải số nguyên tố hay không ? Hãy cùng blog Nguyễn Văn Hiếu đi tìm đáp án nhé .

Khái niệm số nguyên tố

Số nguyên tố là số nguyên dương có duy nhất 2 ước phân biệt là 1 và chính nó. Lưu ý : Số 1 không phải số nguyên tố do chỉ có 1 ước .

Ý tưởng kiểm tra số nguyên tố

1. Nếu số đó bé hơn 2, kết luận không phải số nguyên tố.
2. Đếm số ước của x trong đoạn từ 2 đến căn bậc hai của x. Nếu số đó không có ước nào trong đoạn từ 2 đến căn bậc hai của x thì nó là số nguyên tố. Ngược lại thì không phải. Như vậy, nếu bạn đếm từ 1 thay vì 2 thì x là số nguyên tố khi ta đếm được 1 ước số trong đoạn từ 1 đến căn bậc hai của x.

Tại sao lại chỉ đếm các ước trong đoạn từ 2 đến căn của x?

Nếu bạn chú ý thì 1 số ít nguyên > = 2 bất kể sẽ luôn có số ước ở nửa đầu căn bậc 2 của nó bằng số ước ở nửa sau căn bậc 2 của nó. Cụ thể, những ước sẽ phân bổ thành 2 miền từ [ 2 ; sqrt ( x ) ] và từ [ sqrt ( x ) ; x ] .

Chú ý: Khi kiểm tra bạn nhớ phải là <= sqrt(n) nhé. Nếu chỉ để dấu nhỏ hơn thì các số chính phương như 4, 9 sẽ là số nguyên tố đấy. Tại sao thì bạn thử giải thích xem nào.

012

for(inti=2;i<=sqrt(n);i++)

Ví dụ minh họa

01234567891011121314151617

Vớisố12 .tacósqrt(12)xấpxỉbằng3.464

Đoạn[1;3.464]cóước1,tươngứngđoạn[3.464;12]cóước12/ / 1 * 12 = 12

Đoạn[1;3.464]cóước2,tươngứngđoạn[3.464;12]cóước6/ / 2 * 6 = 12

Đoạn[1;3.464]cóước3,tươngứngđoạn[3.464;12]cóước4/ / 3 * 4 = 12

Trongđoạn[2;3.464]số12chiahếtcho2số(2,3)

=>12khônglàsốnguyêntố

Vớisố9,tacósqrt(9)=3

Đoạn[1;3]cóước1,tươngứngđoạn[3;9]cóước9/ / 1 * 9 = 9

Đoạn[1;3]cóước3,tươngứngđoạn[3;9]cóước3/ / 3 * 3 = 9

Trongđoạn[2;3]số9chiahếtcho1số(3)

=>9khônglàsốnguyêntố

Vớisố7,tacósqrt(7)xấpxỉbằng2.646

Trongđoạntừ[2;2.646]khôngcósốnguyênnàomà7chiahết

=>7làsốnguyêntố.

Dành cho bạn : Tự học lập trình Winform C # qua 10 ứng dụng trong thực tiễn

Code minh họa thuật toán kiểm tra số nguyên tố

Sau đây mình sẽ tiến hành code minh họa sử dụng C / C + +, Java và Python cho những bạn. Các bạn nên tự thử trước khi xem giải thuật. Không nên copy code =))
Kiểm tra số nguyên tố sử dụng C

01234567891011121314151617181920212223242526

/ / Code from http://wp.ftn61.com

#include

#include

intmain(){

intn;

printf(” \ nNhap n = “);

scanf(” % d “,và n ) ;

if(n<2){

printf(” \ n % d khong phai so nguyen to “,n);

return0;

}

int

count=0;

for(inti=2;i<=sqrt(n);i++){

if(n%i==0){

count++;

}

}

if(count==0){

printf(” \ n % d la so nguyen to “,n);

}else{

printf(” \ n % d khong phai so nguyen to “,n);

}

}

Kiểm tra số nguyên tố sử dụng C + +

0123456789101112131415161718192021222324252627

/ / Code from http://wp.ftn61.com

#include

#include

usingnamespacestd;

intmain(){

intn;

cout<<" \ nNhap n = ";

cin>>n;

if(n<2){

cout<

return0;

}

intcount=0;

for(inti=2;i<=sqrt(n);i++){

if(n%i==0){

count++;

}

}

if(count==0){

cout<

}else{

cout<

}

}

Kiểm tra số nguyên tố sử dụng Java

012345678910111213141516171819202122232425262728

/ / Code from http://wp.ftn61.com

publicclassPrimeNumbers{

publicstaticvoidmain(String[]args){

Scanners=newScanner(System.in);

System.out.print(” Enter a number : “);

intn=s.nextInt();

if(isPrime(n)){

System.out.println(n+” is a prime number “);

}else{

System.out.println(n+” is not a prime number “);

}

}

publicstaticbooleanisPrime(intn){

if(n<=1){

returnfalse;

}

for(inti=2;i<=Math.sqrt(n);i++){

if(n%i==0){

returnfalse;

}

}

returntrue;

}

}

Nếu bạn đang học cấu trúc tài liệu và giải thuật, hãy xem ngay series những thuật toán sắp xếp sẽ giúp ích cho bạn đấy .

Source: http://wp.ftn61.com
Category: Tin Tức