Tính tổng các ước của n số nhập vào từ bàn phím

#1

Đề bài như thế này

Tính tổng các ước của n số nhập vào từ bàn phím

Input
Dòng đầu chứa số bộ test.
Các dòng sau, mỗi dòng chứa 1 số nguyên dương n 

Output
Mỗi test in trên 1 dòng chứa 1 số nguyên là tổng các ước của test tương ứng đó.

n: số bộ test mình cần kiểm tra ví dụ:

Input:
2
5
6
Ouput:
6 
12

Đây là Code của em. Cách này tuy đúng nhưng time chạy có vẻ lâu, mọi người còn cách nào chạy nhanh hơn không ạ?? Tối ưu nó càng chạy nhanh càng tốt. Em cảm ơn ạ!!

#include<iostream>
#include<math.h>
using namespace std;
void tong(int &a){
	int s  =0;
	for(int i = 1 ;i <= a; i++){
		if(a % i == 0){
			s += i;
		}		
	}
	cout << s << endl;
}
int main(){
	int n;
	cout << "nhap so n = ";
	cin >> n;
	int b[100];
	cout << "nhap cac so can tinh : ";
	for(int i=0;i<n;i++){
		cin >> b[i];
	}
	cout << "ket qua la : " << endl;
	for(int i=0;i<n;i++){
		tong(b[i]);
	}
}
2 Likes
#2

Anh chưa hiểu cái này là sao @Kudoshinichi, em giải thích kỹ hơn được không?

Em đừng đặt tên là b nha, không có ý nghĩa gì. Em có thể khai báo

int mang_so[100];

Cho anh hỏi thêm, ước là sao ta? Tức là các số chia hết hay sao. Ví dụ 10 có các ước
1 2 5 hả?

1 Like
#3

n: số bộ test mình cần kiểm tra ví dụ:
Input:
2
5
6
Ouput:
6
12

1 Like
#4

Vậy trong bài của em chưa có đọc file?

1 Like
#5

vâng, em sẽ chú ý chỗ mảng :smile:

#6

thì em chỉ chạy vài test thôi anh nên em dùng mảng để nhập từ bàn phím ạ

#7

10 thì là 1,2,5,10 mà anh
:v

#8

em chỉ cần tối ưu sao cho nó chạy nhanh hơn thôi vì em nghĩ cách này cổ xưa quá. Nhưng chưa nghĩ ra .hi

#9

@Kudoshinichi ơi, diễn đàn mình không phải là Facebook, mình không nên viết 1 câu, rồi post một bài như vậy. Như vậy em sẽ thấy là nội dung câu hỏi sẽ bị rời rạc không. Hãy tập trung viết trong một post thôi.

Anh thấy bài em khá ổn đấy, như vậy là được rồi :smile:

1 Like
#10

vâng, em sẽ lưu ý, nhưng có cách nào chạy nhanh hơn ko anh, em muốn giảm cái vòng lặp for kia đi nữa cơ anh ạ

#11 
void tong(int &a){
    int s = 0;
    for(int i = 1 ;i <= a; i++){
        if(a % i == 0){
            s += i;
        }       
    }
    cout << s << endl;
}

Ý em là vòng lặp for này? Anh nghĩ như vậy là ổn

2 Likes
#12

vâng ý em là chỗ đó đấy ạ, giả sử mình cần tính tổng các ước của số 1000 thì nó phải lặp tận 1000 à anh, phải làm sao cho nó chạy nhanh đc đây anh :smiley:

1 Like
#13

Em sửa điều kiện lại thành

for(int i = 1; i <= sqrt(a); i++)

Bời vì nếu giả sử tìm ước của n thì ta có

n / a = b;
=> a*b = n

a lớn nhất khi a == b

=> a <= sqrt(n) (sqrt = căn bậc 2)

2 Likes
#14

ok, tks anh ạ :blush:

1 Like
#16

@Gio Bạn muốn đặt câu hỏi hay sao?

#17

Làm sao chèn Latex để điền công thức toán vậy? Hình như cái này chưa hỗ trợ

1 Like
#18

Cái này chưa hỗ trợ @Gio ơi.

#19

Giờ em ví dụ số 12. Nếu chạy đến sqrt(12) thì sẽ chỉ chạy đến 3,3. Thiếu mất ước bằng 6 anh ạ

#20

Bạn đưa về bài toán phân tích số n thành tích các số nguyên tố. Giả sử số n phân tích thành tích của m số nguyên tố. Thì output sẽ bằng 2 mũ m.

#21

A xl. Mình nhầm một xíu

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