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

#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
#46

tại sao lại phải thêm { } vào lệnh return sau if khi mà nó chỉ đơn thuần là 1 lệnh đơn vậy ạ?! mình là newbie nên chưa hiểu lắm

#47

Thích thì thêm thôi bạn. Cũng đâu có ảnh hưởng gì :smile:

1 Like
#48

vậy ạ?! tại mình ko biết nên hỏi vậy thôi

#49

Vì sau đó thay câu đó bằng hai câu khác là tiêu. goto fail

Vả lại viết không đóng ngoặc như vậy thà viết ngang hàng, nói thật.

1 Like
#50

À cái này mình biết rồi, thế nên mới hỏi là chỉ có 1 lệnh thôi cần gì phải như thế ý

#51 
#include <bits/stdc++.h>
using namespace std;

int a,b;
int prime(int n){
    int m=sqrt(n);
    if (n<2) return 0;
    else if (n>2) {
            if (n%2==0) return 0;
            for (int i=3; i<=m; i+=2)
                if (n%i==0) return 0;
    }
    return 1;
}
int main() {
    #define TASK "ABC"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    cin>>a>>b;
    for (int i=a;i=b;i++)
        if (prime(i)==1) cout <<i<<endl;
        else continue;
    return 0;
}

code của mình có gì sai mà sao ko chạy đc vậy ạ? giúp mình với

#52

Lạy hồn code :pray:

1 Like
#53

mình ngu môn này lắm, bạn nói rõ ràng ra với ạ :((

#54

Bạn xem lại cú pháp vòng for nhé. Bạn for từ đâu đến đâu là do bạn, mình chỉ chỉ bạn được đến vậy thôi.

1 Like
#55

mình fix đc rồi nhé, cám ơn nhiều ạ. mới học nên vậy :frowning:

#56 
bool nguyento(int i)
{
	int j=2;
	if (i==1) 
	{
		return false;
	}
	else
	{
		while (i%j != 0) 
		{
			j+=1;
		}
		if (j<i)
		{
			return true;
		}
		if (j==i)
		{
			return false;
		}
	}
}

mình làm thế này có dc kh nhỉ
chia từ số 2 đến i, nếu gặp số nào mà chia hết thì false, còn chia tới i thì true
cái này mình dùng if cũng dc, nhưng mà sẽ dài dòng hơn dùng while

#57

Không if nổi đâu :smiley:

Mà chỉ cần i chạy tới căn là xác định được, không cần đến n.

2 Likes
#58

Bạn đọc cái này ở đâu vậy ?

#59

nhiều nguồn lắm :V Hoặc tự suy luận cũng ra mà :V

3 Likes
#60

Em tìm nguồn để kiểm chứng thông tin, chứ đọc suông không thì chưa thuyết phục được.

#61

các số tự nhiên có thể viết là:
6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5
ví dụ
0, 1 2, …, 5 thì k = 0,
6,7 8, …, 11 thì k = 1,
v.v.v…

số tự nhiên ko chia hết cho 2 và 3 thì chỉ có thể có dạng 6k+1, 6k+5 (6k, 6k+2, 6k+4 chia hết cho 2, , 6k+3 chia hết cho 3) với k là số nguyên. Ta có thể viết lại 6k+5 thành 6m-1, k, m ở đây cũng như nhau nên có thể nói là 6k +/- 1

cái này intuition cũng rất hợp lý: n số tự nhiên thì hết 1 nửa là số chẵn, trong 1 nửa số lẻ còn lại thì hết 1/3 là số chia hết cho 3, vậy tổng số số ko chia hết cho 2 và 3 là 1 - 1/2 - (1/2 * 1/3) = 1/2 - 1/6 = 1/3. 6k + 1 và 6k - 1 là 2/6 hay 1/3 của n số nguyên rồi. Rất hợp lý :V

có điều xét theo kiểu này thì tăng tốc thêm được có lẽ 17% thôi :V Nếu em chỉ xét số ko chia hết cho 2 thì đã tăng tốc 50% rồi. Xét ko chia hết cho 3 nữa thì tăng tốc 33% của 50% còn lại, hay em chỉ tăng tốc được 17% là hết xí quách. Em có thể xét tiếp các số ko chia hết cho 2,3, và 5 luôn, nhưng tăng tốc càng ít hơn nữa, ko đáng :V

3 Likes
#62

Tìm thử với từ khóa prime number 6x xem ra gì nào!?

#63

Cảm ơn a, nãy giờ tìm keyword của cái này mà không ra.

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