Tối ưu thuật toán tìm số ước nguyên dương của n giai thừa

[BORT_Ddoox (Đỗ Quốc Ân)]

Thuật toán của em;

#include <iostream>
#include <vector>
using namespace std;

const long long mod = 10e9 + 7;
int main() {
	int n;
	cin >> n;
	vector<bool> a(n);
	for (int i = 2; i <= n; i++) {
		a[i] = true;
	}
	for (int i = 2; i <= n; i++ ) {
		if (a[i] == true) {
			for (int j = i*2; j <= n; j += i) {
				a[j] = false;
			}
		}
	} // tao mang a la cac so nguyen to tu 2 den n
	
	long long amount = 1;
	for (int i = 2; i <= n; i++) { 
		long long count = 0;
		if (a[i] == true) {
			for (int j = 2; j <= n; j++) { 
				int num = j;
				while (num%i == 0) { // dem so mu cua tung so nguyen to tu 2 den n
					count++;
					count = count%mod;
					num = num/i;
				}
			}
			amount = (amount*(count + 1))%mod;
		}
	}
	cout << amount;
}

code của em đúng với mấy số bé, nhưng khi lên đến số lớn là nó bị lỗi và giá trị của nó chỉ giới hạn ở kiểu int trong khi em khai báo nó kiểu long long. Mong các cao nhân tối ưu và giải thích lỗi ạ.

[rogp10]

@BORT_Ddoox

const long long mod = 10e9 + 7;

10e9 là có vấn đề vì số lớn cỡ này nhân với nhau sẽ hơn 64 bit.

Mà bạn chỉ cần duyệt qua số nguyên tố thôi, số mũ có thể tính được theo ct cấp số cộng

[BORT_Ddoox (Đỗ Quốc Ân)]

Số mũ tính theo công thức cấp só cộng là sao nhỉ, bác gợi ý cho em với

[rogp10]

1, 2, 3, …, k là k số
Vậy p, 2p, 3p, …, kp là k thừa số p.
Tương tự với số mũ lớn hơn.