[Wiki] Hàm Kiểm Tra số nguyên tố trong C/C++

#64

ví dụ xét số nguyên có dạng 2k+1 thì 12 giây em tiết kiệm được 6 giây, em “tối ưu” thêm nữa chỉ xét số có dạng 6k ± 1 thì em chỉ tiết kiệm được 8 giây, vậy là so với 6 giây tiết kiệm khi chia với số lẻ thì em chỉ tiết kiệm được 2/12 giây, tức là 17% :V Có thể xứng đáng tiết kiệm kiểu này nhưng code lại phức tạp hơn, có khi ko đáng :V

chém gió to hơn nữa: các số nguyên tố > 5 chỉ có thể có dạng 30k + 1, 30k + 7, 30k + 11, 30k + 13, 30k + 17, 30k + 19, 30k + 23, 30k + 29 :V :V :V Số + vào là 1 và số nguyên tố < 30 là bcnn của 2,3,5. Viết lại cho soành điệu 30k ± 1, 30k ± 7, 30k ± 11, 30k ± 13

3 Likes
#65

Này giờ em hiểu sai ý của bạn này, em tưởng là các số nguyên tố trừ 2 và 3 thì có dạng 6k -+ 1, nghe nó hơn vô lý, hóa ra là xem thêm TH thôi :V

#66

người ta ghi 6k mà 2k đâu ra :V :V

3 Likes
#67

Á, nhầm tí haha :)))

#68

Mình thấy phát biểu như vậy cũng đâu có gì sai nhỉ?! :smiley: nếu A thì B nó khác với nếu B thì A.

3 Likes
#69 
#include <stdio.h>
#include <iostream>

using namespace std;
int main()
{
 int SO_KT;
cout<<"Nhap so can kiem tra: " ;
cin >> SO_KT;

if(SO_KT<2) 
	cout <<SO_KT <<" Khong la so nguyen to";

else if(SO_KT==2)
	cout<<SO_KT <<" La so nguyen to" ;
else
{	
int Dem=0;
	for (int i = 3; i < (SO_KT - 1); i += 1){
		if(SO_KT%i==0)
		{
			Dem=1;
			break;
		}
	}
	
	if(Dem==0)
		cout<<SO_KT <<" La so nguyen to";
	else
			cout<<SO_KT <<" Khong la so nguyen to";
}
 
 return 1;
}

1 cách như vậy. Xem bài viết cụ thể hơn

#70

cảm ơn anh, tuy code của anh dài nhưng diễn giải dễ hiểu hơn các code khác. 1 lần nữa cảm ơn anh.

#71

cảm ơn anh, tuy code anh dài nhưng giảng giải dễ hiểu hơn các code khác rất nhiều. 1 lần nữa cảm ơn anh.

#72 
bool nguyento(int n)
{
    if (n<=1) return false;
    for (int i=2;i<=sqrt(n);i++)
        if (n%i==0) return false;
    return true;
}
#73

nếu không dùng sqrt thì bạn cũng có thể chỉnh điều kiện trong vòng lặp thành for (int i=2;i*i<=n;i++)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?