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

#25

Dòng này mình nghĩ sẽ KHÔNG chạy nếu soA bé hơn hoặc bằng 9 vì sqrt(soA) luôn bé hơn hoặc bằng 3. Điều đó có nghĩa chương trình sẽ sai và khi nhập số 9 luôn là số nguyên tố.
Điều chỉnh một chút là <or (int i = 3; i <= sqrt((float)soA); i += 2)

#26

nó thừa sức sàng n <= 10^6 trong 1s mà?

#27

Mình là newbie với programming, có đoạn code tìm số ng tố này mong đc góp ý

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
bool so_nguyen_to(int n);
void main()
{
	int n; char tt;
	lap:
	cout<<"\nNhap n = "; cin>>n;
	
	
	if (so_nguyen_to(n) == true) 
	{
		cout<<"\n"<<n<<" la so nguyen to";
	}
	else {cout<<"\n"<<n<<" khong phai la so nguyen to";}
	
	cout<<"\n";
	cout <<"\nBan co muon kiem tra so khac khong (Bam y de tiep tuc): "; cin>>tt;
	if (tt == 'y' || tt == 'Y') goto lap; else
	system("pause");
}

bool so_nguyen_to(int n)
{
	int i;int count;
	if (n<=3) return true;
	else
	{
		if (n%2 == 0) {return false;}
		count = 0;
		for (i=3;i<n-3;i+=2)
		{
			if (n%i == 0) count+=1;
		}
		if (count > 0) {return false;} else {return true;}
	}
}
#28

Sao 1 số chỗ bị lỗi nhỉ copy ko đc

cout<<"\n Nhap n"; cin>>n;
#29

Vậy thì bạn đọc lại post #1 nhé.

#30

Mình thì thường dùng cách này thôi, không tối ưu mấy

bool soNguyenTo(int soA) {
    soA=abs(soA);
    if (!soA) return false;
    if (soA>=3 && !(soA%2)) return false;
    for (int i=3; i<=sqrt(soA); i+=2) if (!(soA%i)) return false;
    return true;
}
Phương pháp tối ưu để tìm số nguyên tố
#31

Dòng 3 có logic khá lắt léo.

1 Like
#32

Thuật toán số nguyên tố, mình cứ liệt kê từng bước đi:
Đầu vào, mình có tập hợp các số tự nhiên từ 1 đến n
Kết quả: Cần lọc ra những số nguyên tố.

  1. Giả sử thuật toán chạy được từ 1 đến n-1 rồi, ta đặt tên là x, ta làm bước n, bằng cách:
    xem n có chia hết các số trong x không, nếu không thì thêm n vào kết quả cuối cùng, còn không thì thôi.
  2. Với trường hợp gốc, ta có 2 là số nguyên tố.
    Với thuật toán đệ quy này, các bạn xem có thể tối ưu được không nhé :slight_smile:
#33

Chạy đến căn n thôi, cái này chỉ là đổi cận không liên quan.

Thực ra với bài đó thì sàng sẽ tốt hơn.

1 Like
#34

anh cho em hỏi?
chạy vậy trường hợp bằng 2 thì xét sao vậy anh

#35

Thì bạn phải if n < 4 trước, sau đó lấy n mod 2.

#36

Hàm này nhập vào số khác 0 đều trả về false mà :sweat_smile:

#37

Oke :smile: dòng này thiếu dấu !

if (!soA) return false;
#38

Cho em hỏi tại sao lại dùng i+=2 mà ko fải là i++ vậy

#39

Chỉ tính các số lẻ, các số chẵn thì chắc chắn k phải số nguyên tố rồi. Giảm bớt số cần kiểm tra.

1 Like
#40

ai giúp em giải thích cái code tìm số nguyên tố trong khoảng m,n này đc ko? em đọc mà thấy nó mung lung ntn ấy :3

int main ()
{
	int N;
	scanf("%d",&N);//nhap vao so gia tri
 
	while(N--)
	{
		int m,n,d,i;// gia tri m, n la gia tri ban dau
		//d la so gia tri can xac minh
		//i vong lap
		
		scanf("%d %d",&m,&n);
		if(m==1)m=2;
		d = n-m+1;
		bool * a = new bool[d];// cap phat bo nho cho a.
		for(i =0;i<d;i++)a[i]=true;
 
		for( i = m%2;i<d;i+=2)a[i]=false;
 
		for(i = 3; i*i<=n;i+=2)
		{
			if(i>=m && !a[i-m])continue;
			int j = m/i*i;
			if(j<m)j+=i;
			if(j==i)j+=i;
 
			j-=m;
			for(;j<d;j+=i)
			{
				a[j]=false;
			}
		}
 
		for(i=m;i<=n;i++)
		{
			if(i==1)a[i-m]=false;
			if(i==2)a[i-m]=true;
			if(a[i-m])printf("%d\n",i);
		}
		if(N)printf("\n");
	}
	return 0;
}
#41

Đây gọi là sàng Eratosthenes :slight_smile: bạn tìm hiểu xong về tự viết lại thôi.

Thực ra nếu chỉ cần đoạn [m…n] thì dùng sàng phân đoạn chứ viết ntn hao mem mà chậm nữa.

2 Likes
#42

mọi người ơi qua vụ gõ nhầm mà em giải được bài này trong đoạn Code cực ngắn, nhưng em cũng chả hiểu logic đằng sau nó là tn?

int lasonguyento(int x)
{
	int i;
	cin >> x;
	for(i=1;i<x;i++)
	if(x&i!=0  ) // o day minh dinh viet dau %, cuoi cung danh nham thanh dau &
		{cout << "  la so nguyen to" << endl; return 0;}
	else x&i==0;
		{cout << " khong la so nguyen to" << endl;}
	return 1;
}

int main()
{
	int x;
	lasonguyento(x);
	return 0;
}
#43

Code bạn sai rồi.

  • Nhập vào 25. Bạn sẽ thấy bạn sai chứ chẳng đúng vào đâu cả!

  • Đoạn này

Bạn định làm gì ở đây?

  • & là toán tử bitwise AND. Tìm hiểu trên mạng nhé.
#44

Chắc bạn nhập 3 5 7 thôi phải không. Vì x & 1 chỉ là kiểm tra chẵn lẻ thôi.

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