XTU 1377 Factorization

Factorization 题目描述根据质因子唯一分解定理可知n=pk11pk22…pkmm，其中pi都是质数。我们定义f(n)=m, 求g(a,b)=∑bi=af(n)。输入第一行是一个整数T(1≤T≤1000)，表示样例的个数。以后每个样例占一行，为两个整数 a(2≤a≤b≤106)。输出依次每行输出一个样例的结果，为一个整数。样例输入 2 2 2 2 10 样例输出 1 11

Sample Input


Sample Output

原代码如下：

#include
int Prime[1000001] = { 0 };//下标为素数
int prime[1000001] = { 0 };//放素数
int primenum[1000001] = { 0 };//存放下标对应的m
void IN();//初始化素数
void save();
int search(int num);
void Save();
int main()
{
    int T;
    IN();
    save();
    Save();
    scanf_s("%d", &T);
    while (T--) {
        int a, b;
        scanf_s("%d %d", &a, &b);
        printf("%dn", primenum[b] - primenum[a - 1]);
    }
    return 0;
}
int search(int num) {
    int m = 0, i = 0;
    while (num != 1) {
        int flag = 0;
        while (num % prime[i] == 0) {
            num /= prime[i];
            if (flag == 0)flag = 1;
        }
        if (flag)m++;
        i++;
    }
    return m;
}
void save() {
    for (int i = 2; i <= 1000000; i++)
        primenum[i] = search(i);
}
void Save() {
    for (int i = 3; i <= 1000000; i++)primenum[i] += primenum[i - 1];
}
void IN() {
    int i, j, n = 0;
    for (i = 2; i <= 1000000; i++)Prime[i] = 1;
    for (i = 2; i <= 1000000; i++)
        if (Prime[i])
            for (j = 2; i * j <= 1000000; j++) Prime[i * j] = 0;
    for (i = 2; i <= 1000000; i++)
        if (Prime[i])prime[n++] = i;
}

遇到问题：

1、超时

修改后代码如下：

#include
int Prime[1000001] = { 0 };//下标为素数
int prime[1000001] = { 0 };//放素数
int primenum[1000001] = { 0 };
int n = 0;
void IN();//初始化素数
void save();
int search(int num);
void Save();
int main()
{
    int T;
    IN();
    save();
    Save();
    scanf_s("%d", &T);
    while (T--) {
        int a, b;
        scanf_s("%d %d", &a, &b);
        printf("%dn", primenum[b] - primenum[a - 1]);
    }
    return 0;
}
int search(int num) {
    int m = 0, i;
    for (i = 0; i < n && prime[i] * prime[i] <= num; i++) {
        if (num % prime[i] == 0) {
            m++;
            while (num % prime[i] == 0)num /= prime[i];
        }
    }
    if (num != 1)m++;
    return m;
}
void save() {
    for (int i = 2; i <= 1000000; i++)
        primenum[i] = search(i);
}
void Save() {
    for (int i = 3; i <= 1000000; i++)primenum[i] += primenum[i - 1];
}
void IN() {
    int i, j;
    for (i = 2; i <= 1000000; i++)Prime[i] = 1;
    for (i = 2; i <= 1000000; i++)
        if (Prime[i])
            for (j = 2; i * j <= 1000000; j++) Prime[i * j] = 0;
    for (i = 2; i <= 1000000; i++)
        if (Prime[i])prime[n++] = i;
}

开始的时候不断超时，没想到存了数据后search函数太慢的，导致还是超时。

最后还是有劳一位大佬相助得以解决

XTU 1377 Factorization

C/C++/C#相关栏目本月热门文章