C程序优化/速度提高

作为初学者，我编写了一个程序，用于查找不高于输入自然数（x）的素数（prime）。该程序工作正常（我认为），但我想让它工作得更快（对于更高的数字）。这有可能，如果是的话，如何？C程序优化/速度提高

#include <stdio.h> 

int main() { 
    int x, i, j, flag = 1, prime = 0 ; 

    scanf("%d", &x); 
    for (i = 2; i <= x; i++) { 
     j = 2; 
     while (flag == 1 && j < i/2 + 1) { 
      if (i % j == 0) { 
       flag = 0; 
      } 
      j++; 
     } 
     if (flag == 1) { 
      prime++; 
     } 
     flag = 1; 
    } 
    printf("%d\n", prime); 
    return 0; 
}

来源

2015-10-16 Panagiotis Papantonakis

1：找到一个更好的算法。 2.对于你当前的算法，注意只有一个偶素。 3.对于你当前的算法，请注意，如果你在第一个'sqrt（n）'数字中没有找到除数，'n'就是质数。 – EOF

制作到目前为止发现的每个素数的列表或数组。只能测试它们作为除数。如果'6'是一个除数，如果它已经通过'2'和'3'作为除数，那么没有必要进行测试。 –

查看Eratosthenes的筛子。您可以基于此构建更高效的算法。 –

你的算法做试划分，这很慢。一个更好的算法是埃拉托色尼的2000岁筛：

function primes(n): 
    sieve := makeArray(2..n, True) 
    for p from 2 to n 
     if sieve[p] 
      output p # prime 
      for i from p*p to n step p 
       sieve[i] := False

我要把它留给你翻译成C.如果你想知道更多，我虚心推荐文章Programming with Prime Numbers在我的博客。

来源

2015-10-17 01:23:17 user448810

对于我从p + p到n步骤p，我应该从'p + p到n步骤p'吗？ –

@WeatherVane no。 –

@WillNess是的，我看到......'p + p'由'2'照顾。 'p + p + p'由'3'等来处理。 –

有一个着名的素数定理。它指出

π(n)≈n/ln(n)

但是有一些算法来计算这个函数。跟随链接： PNT

Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method

来源

2015-10-17 02:58:26 user2979190

C程序优化/速度提高

回答

相关问题