我在Project Euler中尝试过这个问题，我需要计算所有素数的和，直到两百万。
这就是我提出的解决方案-
#include <stdio.h>
int main() {
long sum = 5; // Already counting 2 and 3 in my sum.
int i = 5; // Checking from 5
int count = 0;
while (i <= 2000000) {
count = 0;
for (int j = 3; j <= i / 2; j += 2) {
// Checking if i (starting from 5) is divisible from 3
if (i % j == 0) { // to i/2 and only checking for odd values of j
count = 1;
}
}
if (count == 0) {
sum += i;
}
i += 2;
}
printf("%ld ", sum);
}
运行大约需要480秒，我想知道是否有更好的解决方案或技巧来改进我的程序。
________________________________________________________
Executed in 480.95 secs fish external
usr time 478.54 secs 0.23 millis 478.54 secs
sys time 1.28 secs 6.78 millis 1.28 secs
只需两个小小的修改，您的代码就会变得更快：
#include <stdio.h>
#include <math.h>
int main() {
long long sum = 5; // we need long long, long might not be enough
// depending on your platform
int i = 5;
int count = 0;
while (i <= 2000000) {
count = 0;
int limit = sqrt(i); // determine upper limit once and for all
for (int j = 3; j <= limit; j += 2) { // use upper limit sqrt(i) instead if i/2
if (i % j == 0) {
count = 1;
break; // break out from loop as soon
// as number is not prime
}
}
if (count == 0) {
sum += i;
}
i += 2;
}
printf("%lld ", sum); // we need %lld for long long
}
所有解释都在评论中。
但肯定有更好甚至更快的方法可以做到这一点。
我在我10年前的MacPro上运行了这个程序，对于2000万的第一次Prime，大约需要30秒。
该程序计算几乎立即(即使在调试…中(200万的总和，只需要一秒钟就可以达到2000万(Windows 10，10年前的i7@3.4 GHz，MSVC 2019(。
注意：没有时间设置我的C编译器，这就是为什么malloc上有一个强制转换。
"；"大"；优化是存储平方值AND素数，所以绝对不会测试不可能的除数。由于在给定的整数区间内不超过1/10的素数(启发式，健壮的代码应该测试这一点，并在需要时重新分配primes数组(，因此时间大大缩短。
#include <stdio.h>
#include <malloc.h>
#define LIMIT 2000000ul // Computation limit.
typedef struct {
unsigned long int p ; // Store a prime number.
unsigned long int sq ; // and its square.
} prime ;
int main() {
prime* primes = (prime*)malloc((LIMIT/10)*sizeof(*primes)) ; // Store found primes. Can quite safely use 1/10th of the whole computation limit.
unsigned long int primes_count=1 ;
unsigned long int i = 3 ;
unsigned long long int sum = 0 ;
unsigned long int j = 0 ;
int is_prime = 1 ;
// Feed the first prime, 2.
primes[0].p = 2 ;
primes[0].sq = 4 ;
sum = 2 ;
// Parse all numbers up to LIMIT, ignoring even numbers.
// Also reset the "is_prime" flag at each loop.
for (i = 3 ; i <= LIMIT ; i+=2, is_prime = 1 ) {
// Parse all previously found primes.
for (j = 0; j < primes_count; j++) {
// Above sqrt(i)? Break, i is a prime.
if (i<primes[j].sq)
break ;
// Found a divisor? Not a prime (and break).
if ((i % primes[j].p == 0)) {
is_prime = 0 ;
break ;
}
}
// Add the prime and its square to the array "primes".
if (is_prime) {
primes[primes_count].p = i ;
primes[primes_count++].sq = i*i ;
// Compute the sum on-the-fly
sum += i ;
}
}
printf("Sum of all %lu primes: %llun", primes_count, sum);
free(primes) ;
}
您的程序可以通过提前停止内部循环来轻松改进：
- 当
i超过sqrt(j)时 - 当找到除数时
还要注意，类型long可能不够大，无法满足所有体系结构的总和。推荐使用long long。
这是一个修改版本：
#include <stdio.h>
int main() {
long long sum = 5; // Already counting 2 and 3 in my sum.
long i = 5; // Checking from 5
while (i <= 2000000) {
int count = 0;
for (int j = 3; j * j <= i; j += 2) {
// Checking if i (starting from 5) is divisible from 3
if (i % j == 0) { // to i/2 and only checking for odd values of j
count = 1;
break;
}
}
if (count == 0) {
sum += i;
}
i += 2;
}
printf("%lldn", sum);
}
这个简单的更改大大减少了运行时间！2000000:的速度比快1000倍
chqrlie> time ./primesum
142913828922
real 0m0.288s
user 0m0.264s
sys 0m0.004s
然而，请注意，试验划分的效率远低于埃拉托斯梯尼的经典筛选。
这里有一个简单的版本：
#include <stdio.h>
#include <stdlib.h>
int main() {
long max = 2000000;
long long sum = 0;
// Allocate an array of indicators initialized to 0
unsigned char *composite = calloc(1, max + 1);
// For all numbers up to sqrt(max)
for (long i = 2; i * i <= max; i++) {
// It the number is a prime
if (composite[i] == 0) {
// Set all multiples as composite. Multiples below the
// square of i are skipped because they have already been
// set as multiples of a smaller prime.
for (long j = i * i; j <= max; j += i) {
composite[j] = 1;
}
}
}
for (long i = 2; i <= max; i++) {
if (composite[i] == 0)
sum += i;
}
printf("%lldn", sum);
free(composite);
return 0;
}
此代码是2000000:的另一个20倍速度
chqrlie> time ./primesum-sieve
142913828922
real 0m0.014s
user 0m0.007s
sys 0m0.002s
对于较大的边界，可以在许多方面进一步改进筛选方法。