Tìm các số mà nếu chia hết cho một số nguyên tố nào đó thì cũng chia hết cho bình phương của số nguyên tố đó

#1

Viết chương trình liệt kê các số đẹp như vậy trong đoạn giữa hai số nguyên dương cho trước.
INPUT
1 50
OUTPUT
4 8 9 16 25 27 32 36 49

Code của mình như sau

#include <stdio.h>
#include <math.h>

bool isPrime(int n)
{
	if(n<2)
		return false;
	for(int i=2 ; i*i<=n ; i++){
		if(n%i==0)
			return false;
	}
	return true;
}

int ChiaHet(int m, int n)
{
	for(int i= m ; i<=n ; i++)
	{
		for(int d = 2; d <= 10; d++)
		{
			if (isPrime(d) == true)
			{
				if(i % d == 0 && i % d*d == 0)
				{
					printf("%d ",d);
				}
			}
		}
	}
}


int main()
{
	int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
	ChiaHet(m,n);

    return 0;
}

Nhưng mình kiểm tra thì không ra đúng kết quả. Các bạn giúp mình tìm lỗi với?

#2

Tại sao ở đây chỉ cho d chạy từ 2 đến 10 ạ. Số nguyên tố thì có thể lớn hơn 10 mà

Em góp ý 1 chút thôi. Nếu không phải hàm trả về thì để void chứ để int xong trả về cái gì ạ
Còn về phần bài này sai ở đâu thì có các chỗ:

Cái này phải là i % (d * d) == 0. Anh xem lại độ ưu tiên của các toán tử.

Chỗ này phải in ra i chứ không phải d
Sửa lại:

printf( "%5d" , i);

Chốt lại em xin phép sửa lại hàm ChiaHet như sau ạ:

void ChiaHet(int m, int n)
{
	for(int i= m ; i<=n ; i++)
	{
		for(int d = 2; d <= sqrt( i ) ; d++)
		{
			if (isPrime(d) == true)
			{
				if( i % (d * d) == 0)
				{
					printf("%d ", i);
					break; // tránh lặp số
				}
			}
		}
	}
}

Em mới tìm được từng này. Bác nào tìm được thêm thì góp ý ạ.
P/s : anh xem lại cách đặt tiêu đề trong quy( hay qui nhỉ) định ạ

2 Likes
#3

Thực sự bạn chưa hiểu đề :slight_smile:

Tìm n sao cho \forall p \in \mathbf{P},\ p \mid n \Rightarrow p^2 \mid n

Bài này sinh đệ quy rồi thảy vào heap khá ổn.

5 Likes
#4

Em có ý kiến 1 chút ạ.

Về biểu thức anh viết thế này thì em nghĩ là viết theo đề kia đối với bạn ấy dễ hiểu hơn vì chắc bạn ấy mới chỉ cấp 3 như em và mới tự học lập trình. Có những kí hiệu lớp trên có thể hiểu nhưng không phải ai lớp dưới khi nhìn kí hiệu cũng hiểu được ạ. :man_facepalming: :man_facepalming:

Còn cái này thì bạn còn đang nhầm lẫn về độ ưu tiên các toán tử và khả năng chưa phân biệt được các kiểu dữ liệu, chưa biết hàm trả về và hàm không trả về khác nhau chỗ nào (Khả năng thôi ạ. Đúng hay không thì chủ thớt vào xác minh ) thì chắc chưa học đệ quy đâu anh.

3 Likes
#5

trước khi bạn code, bạn cần phân tích bài toán, đừng vội code khi chưa biết phải code gì

  1. chia hết cho một số nguyên tố
  2. chia hết cho bình phương số nguyên tố đó

điều kiện 2 đã bao gồm luôn điều kiện 1

ta có các số nguyên tố 2 3 5 7 …
=> bình phương cách số đó 4 9 25 49

duyệt các số trong range, với mỗi số kiểm tra xem có chia hết cho bất kì số nào trong list số bình phương của các số nguyên tố không là xong

một số challenge tối ưu cho bài toán (với n không quá lơn, < 10^5)
chi phí để tìm các số nguyên tố trong khoảng 2 - n => O(n)
tìm tất cả các bội số của các bình phương => O(n)
chi phí để đếm số lượng số trong một đoạn => O(1) (quy hoạch động, setup O(n))

final cost: O(n)

8 Likes
#6

là dãy số này: https://oeis.org/A001694

5 Likes
#7

Số này không có tên tiếng Việt mà nhỉ?

À mà “quy” mới đúng.

4 Likes
#8

Kí hiệu \forall thì dễ hiểu mà, còn kí hiệu chia hết | thì cấp 2 học rồi chứ có phải chưa học đâu.

2 Likes
#9

Em lớp 10 rồi em nhìn không hiểu luôn🤦🤦🤦. Chắc tại chưa dùng mấy nên không nhớ🤦🤦🤦.

#10

Đầu lớp 10 có ôn lại mà :smiley:

2 Likes
#11

Sao em không thấy nhỉ :thinking::thinking:. Tụi em không thấy ôn luôn🤦. Em dùng chia hết toàn 3 chấm thẳng ấy. Cái này thấy lần đầu nên lạ lạ🤦

1 Like
#12

Chia hết cho \vdots trong tex viết là \vdots thì phải.
6 \vdots 3 (dấu lại cao hơn số rất mất thẩm mĩ :smiley: chịu thôi)

“6 chia hết cho 3” cũng như là “3 chia hết 6” là 3 \mid 6 hay 3 \mid 6.

Làm như này dính chưởng số 12 (hoặc 20) ngay :smiley:

4 Likes
#13

số 12 và 20 thì sao vậy bạn?

#14

Vì bạn sẽ để lọt thừa số 5 trong 20.

3 Likes
#15
  • 3 | 12 nhưng 3^2\not{|}\ 12.
  • 5 | 20 nhưng 5^2\not{|}\ 20.
2 Likes
#16

à đã hiểu, do mình hiểu sai đề

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