这道题 projetceuler 上好像有人发现相邻偶数值项的比例为黄金比例

第三题的算法还可以优化

q3

#include <stdio.h>
#include <math.h>

int prime[1024];
int primeNum = 0;

//只能用于判断递增的数, 同时生成质数表
bool IsPrime(int x)
{
    if (x == 2)
    {
        prime[primeNum++] = x;
        return true;
    }
   
    int idx = 0, n = (int)sqrt((float)x) + 1;
    for (; prime[idx] < n; idx++)
    {
        if (x % prime[idx] == 0)
        {
            return false;
        }
    }

    prime[primeNum++] = x;
    return true;
}

int main()
{
    long long num = 600851475143;
    int idx = 2, ret = -1;
   
    for( ; idx <= num; idx++)
    {
        if (IsPrime(idx))
        {
            while (num % idx == 0)    // 可能有相同的质因子
            {
                num /= idx;
                ret = idx;
            }
        }
    }

    printf("%d\n", ret);

    return 0;
}

 

[ 本帖最后由 jimmywood 于 2011-6-23 17:16 编辑 ]

数据规模太小了，再优化，也看不出来。

那倒是，这种优化就是个蛋疼的嗜好

要沉没了，顶一顶。
为什么贴代码的人这么少

第一题很水，范围太小了，数学方法没考虑过，但是至少dp可以做到O(logN) （大数基本运算的复杂度不考虑在内）
第二题也很水，也是范围太小了，如果将大数基本运算的复杂度不考虑在内，可以做到O(logN)
至于第三题，分解质因数的优秀算法google一下很多，我记得算法导论上也有。

第一题我的复杂度应该是O(1)吧。跟 N 是没有关系的最后的计算。

囧，对，第一题如果数学方法可以O(1)

有趣的题。第一题第二题很简单，下面给出算法。第三题大数的因式分解，我也没有很好的算法，和大家属于一个数量级。
正在看非诚勿扰，呵呵如果大家感兴趣，一会儿解释算法。

#include<stdio.h>
#include<math.h>

#define SQRT_5    2.2360679774997896964091736687313
#define A        ((1 + SQRT_5) / 2)
#define B        ((1 - SQRT_5) / 2)


int Test1(int n) //计算1－N以内（包括N）能被3和5整除的整数的和
{
    int i, a3, a5, a15;
    //n--;//如果不包括N请取消这行的注释
    i = n / 3;
    a3 = (3 * (i + 1) * i) >> 1;
    i = n / 5;
    a5 = (5 * (i + 1) * i) >> 1;
    i = n / 15;
    a15 = (15 * (i + 1) * i) >> 1;
    return a3 + a5 - a15;
}

int Test2(int a) //计算小于等于a的fibonacci数列中的值为偶数的项的和
{
    double x, y, sf;
    int n, t;
    
    x = log(SQRT_5 * a) / log(A);
    x += 0.5;
    n = (int)x;
    y = (pow(A, n) - pow(B, n)) / SQRT_5;
    y += 0.5;
    t = (int)y;
    if(t > a) n--;
    sf = ((SQRT_5 + 1) / (SQRT_5 - 1) * (pow(A, n) - 1) - (1 - SQRT_5) / (1 + SQRT_5) * (1 - pow(B, n))) / SQRT_5;
    sf += 0.5;
    
    return ((int)sf) / 2;
}

int main()
{
    printf("%d\n", Test1(1000));
    printf("%d\n", Test2(4000000));
    return 0;
}