Euler Totient：优化

2013-11-01 20 views 1 likes

int main(void) 
{ 
    int n, div, a, b; 
    double phi; 
    printf("Enter n:\n"); 
    if (scanf("%d", &n) < 1 || n <= 0) 
    { 
    printf("Wrong input.\n"); 
    return 1; 
    } 

    a = n; 
    div = 2; 
    phi = n; 

    while (n != 1) 
    { 
    if (n % div != 0) 
     div++; 
    else 
    { 
     n = n/div; 
     if (b != div) 
     { 
     b = div; 
     phi = phi * (1.0 - 1.0/div); 
     } 
    } 
    } 

    printf("phi(%d) = %.f\n", a, phi); 

    return 0; 
}

这是我作为一个学校任务制作的欧拉斯托特的代码。该计划似乎运行良好，但仍然缓慢。我怎样才能让它更快？Euler Totient：优化

来源

2013-11-01 Le Nguyen Duy Anh

你是否介绍了密码？你知道瓶颈在哪里吗？ – Floris

你应该在进入循环之前初始化'b'？它在被赋值之前在'if（b！= div）'行被访问。可能不是缓慢的原因...你能给我们一个预期的vs实际速度的想法吗？你有没有尝试用'-O3'标志编译？ – Floris

速度有多慢？它需要多快？ – DaV

回答

首先检查div=2。

之后，你只需要检查奇数，所以你可以使用div += 2。这应该把时间减半。

来源

2013-11-01 13:00:59

我不确定是否有更好的算法，但我们可以从低挂的水果开始：您正在测试所有数字，最高为n以找到它的除数。这是多余的，从φ（n）的定义我们知道我们只需要它的主要因素。

很好，可以说，我们只是将线性搜索转化为超多项式问题。

不一定。

采取P6总理候选人发生器：

def P6(): 
    yield 2 
    yield 3 
    i = 5 
    while True: 
     yield i 
     if i % 6 == 1: 
      i += 2 
     i += 2

，让我们建立在它之上的一个分解函数：

def factors(n): 
    d = {} 
    primes = p6() 
    for p in primes: 
     while n % p == 0: 
      n /= p 
      d[p] = d.setdefault(p, 0) + 1 
     if n == 1: 
      return d

现在发现φ（n）是微不足道的。尝试在C中实现并测量差异。如果你需要它更快，像GMP这样的库可以提供更快的因式分解例程。

来源

2013-11-01 13:37:31

Euler Totient：优化

回答

相关问题