| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1651 人关注过本帖
标题:小黑 进来 单独pk
只看楼主 加入收藏
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
只算因数个数的话,能简化到分解质因数

[ 本帖最后由 azzbcc 于 2013-3-20 15:20 编辑 ]


[fly]存在即是合理[/fly]
2013-03-20 15:18
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
以下是引用azzbcc在2013-3-20 15:18:38的发言:

只算因数个数的话,只能简化到分解质因数
关键是时间啊   如何能做到用时最少

DO IT YOURSELF !
2013-03-20 15:19
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
这是我能想到的极限了
程序代码:
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>

int a[240] = {0};

void InitArray(int n)
{
    int i, temp = 2, j;

    for (i = a[0];i > 0;a[i--] = 0);
    for (i = 2, j = 1;n != 1;++i)
    {
        if (n % i)    continue;
        if (temp != i)
        {
            j += !!a[j];
            temp = i;
        }
        n /= i--, ++a[j];
    }
    a[0] = j;
}
int main()
{
    clock_t t2, t1 = clock();

    int j, temp;
    for (int i = 1000000;i > 240;--i)
    {
        InitArray(i);
        for (temp = j = 1;j <= a[0];++j)
            temp *= a[j] + 1;
        if (temp == 240)    printf("%d\t", i);
    }
    puts("");

    t2 = clock();
    printf("%.3f s\n", (t2-t1)/1000.0);
    return 0;
}

思路是质因数分解,求因数个数

[ 本帖最后由 azzbcc 于 2013-3-20 16:06 编辑 ]


[fly]存在即是合理[/fly]
2013-03-20 16:01
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
嗯,还能把 sqrt(n)以内的质数先罗列出来,这样更快些

这段代码 729 s


[fly]存在即是合理[/fly]
2013-03-20 16:11
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
以下是引用azzbcc在2013-3-20 16:11:10的发言:

嗯,还能把 sqrt(n)以内的质数先罗列出来,这样更快些
 
这段代码 729 s
那要是1亿
大约72900秒 20个小时左右

DO IT YOURSELF !
2013-03-20 16:15
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 


不止100倍,我先写写指数罗列的情况


[fly]存在即是合理[/fly]
2013-03-20 16:24
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
差距蛮大的,缩短到 12秒,正在测试 1亿、、、


[fly]存在即是合理[/fly]
2013-03-20 16:45
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
程序代码:
#include <time.h>
#include <math.h>
#include <stdio.h>

int a[240] = {0};
int ss[1230] = {2, 3, 5, 7, 11, 13, 17, 19};

void Init()
{    //10000以内质数表,1229个
    int i, j, k = 8, temp;
    for (i = 23;k != 1230;i += 2)
    {
        temp = (int)sqrt(i);
        for (j = 0;ss[j] <= temp;++j)
        {
            if (i % ss[j])    continue;
            break;
        }
        if (ss[j] <= temp)    continue;
        ss[k++] = i;
    }
}
void InitArray(int n)
{   //把 n分解质因数,指数部分依次存入数组 a,a[0]存储有效数位
    // 例如 240 = 2 ^ 4 * 3 * 5,则 数组 a:3 4 1 1
    int i, temp = 2, j;
    int s = (int)sqrt(n);
    
    for (i = a[0];i > 0;a[i--] = 0);    //数组 a清 0
    for (i = 0, j = 1;n != 1 && ss[i] <= s;++i)
    {
        if (n % ss[i])    continue;
        if (temp != ss[i])
        {
            j += !!a[j];
            temp = ss[i];
        }
        n /= ss[i--], ++a[j];
    }
    if (1 != n)    ++a[j += !!a[j]];
    a[0] = j;
}
int main()
{
    clock_t t2, t1 = clock();

    int j, temp;Init();
    for (int i = 100000000;i >= 240;--i)
    {
        InitArray(i);

        //按数组 a求出因数个数,240的因数个数为 (4+1)*(1+1)*(1+1) = 20
        for (temp = j = 1;j <= a[0];++j)
            temp *= a[j] + 1;

        if (temp >= 240)    printf("%10d\t", i);
    }
    puts("");

    t2 = clock();
    printf("%.3f s\n", (t2-t1)/1000.0);
    return 0;
}


[ 本帖最后由 azzbcc 于 2013-3-20 23:18 编辑 ]


[fly]存在即是合理[/fly]
2013-03-20 17:20
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
无力了、、、



[fly]存在即是合理[/fly]
2013-03-20 17:35
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
太高了 太深了

梅尚程荀
马谭杨奚







                                                       
2013-03-20 21:34
快速回复:小黑 进来 单独pk
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027121 second(s), 7 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved