回 帖 发 新 帖 刷新版面

主题:求m到n所有整数的全部因数个数之和


     设1《m《n《10的八次方,求m到n所有整数的全部因数个数之和。
            
     如:m=3,n=6
    
         输出:11

回复列表 (共4个回复)

沙发

说清楚一点这里因数是什么?说一个当m=3,n=6输出11是怎么算的。

板凳

明白了意思3的因数是指1 3 ,4的因数是1 2 4。这个程序 时在linux gcc环境下编译成功的。
#include <stdio.h>
#include <stdlib.h>
#define MIN 1
#define MAX 100000000
int is_prime(int m);
int main()
{
    int sum = 0;
    int i,j;
    unsigned int lower;
    unsigned int upper;
    printf("输入下界:");
    scanf("%d",&lower);
    printf("输入上界:");
    scanf("%d",&upper);
    if(lower < MIN || upper > MAX || lower > upper){
        perror("输入错误!\n");
        exit(1);
    }else{
        for(i = lower; i <= upper; i++){
            if(is_prime(i))
                sum += 2;
            else{
                sum += 2;
                for(j=2;j < i; j++){
                    if( i % j == 0)
                        sum += 1;
                }
            }
        }
    }
    printf("%d 到 %d 之间因数个数的和为 %d\n",lower,upper,sum);
    return 0;
}

int is_prime(int m)
{
    int j = 1;
    int i;
    for(i = 2; i < m ;i++){
        if( m % i == 0){
            j--;
            break;
        }
    }
    return j;
}

3 楼

这个题好像是AC的一道题,注意运行时间,ls的思路是对的,不过数字太大,毕竟10^8,就不知道了。

4 楼

// 下面我写的这个程序运算(m=1,n=100000000)在我的电脑上15秒左右。
// 不知道还有没有更快的算法
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <malloc.h>

int main()
{
    unsigned int    *v;
    unsigned char    *count;
    int sum = 0;
    int i,j;
    int    low, high;
    int    temp;
    int    k;
    
    printf("Input lower bound: ");
    scanf("%d", &low);
    printf("Input upper bound: ");
    scanf("%d", &high);
    
    v = (unsigned int*)malloc(sizeof(unsigned int)*(high+1));
    count = (unsigned char*)malloc(sizeof(unsigned char)*(high+1));
    
    int    t = clock();
    
    for(i=1; i<=high; ++i)
    {
        v[i] = i;
        count[i] = 1;
    }
    
    if(low == 1)
        count[low] = 1;
    
    int    prime = 2;
    int root = (int)(sqrt(high+0.5));
    
    while(prime <= root)
    {
        if(prime == 2)
        {
            for(i=prime; i<=high; i+=prime)
            {
                temp = 1;                
                while(!(v[i] & 1))
                {
                    ++temp;
                    v[i] >>= 1;
                }
                count[i] *= temp;
            }
        }
        else
        {
            k = prime;
            temp = 2;
            while(k>0 && k <= high)
            {
                for(i=k; i<=high; i+=k)
                {
                    v[i] /= prime;
                    count[i] /= temp-1;
                    count[i] *= temp;
                }
                ++temp;
                k *= prime;
            }
        }

        // find the next prime
        for(i=prime+1; i<=high; ++i)
        {
            if(v[i] > 1)
            {
                prime = v[i];
                break;
            }
        }
    }
    
    for(i=low; i<=high; ++i)
    {
        if(v[i] > 1)
            count[i] <<= 1;
        sum += count[i];
    }
    
    t = clock()-t;
    
    printf("sum=%d, time=%d\n", sum, t);
    
    free(v);
    free(count);
    return 0;
}

我来回复

您尚未登录,请登录后再回复。点此登录或注册