我已經從Project Euler中嘗試過這個問題，我需要計算所有素數的總和直到 200 萬。
這是我想出的解決方案-
#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
uj5u.com熱心網友回復：
通過兩個小修改，您的代碼變得更快：
#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 萬個第一次素數大約需要 30 秒。
uj5u.com熱心網友回復：
該程式幾乎立即計算（即使在除錯中...）200 萬的總和，2000 萬只需要一秒鐘（Windows 10、10 歲的 i7 @ 3.4 GHz、MSVC 2019）。
注意：沒有時間設定我的 C 編譯器，這就是為什么在malloc.
“大”優化是存盤平方值和素數，因此絕對不會測驗不可能的除數。由于在給定的整數區間內不超過 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: %llu\n", primes_count, sum);
free(primes) ;
}
uj5u.com熱心網友回復：
您的程式可以通過提前停止內部回圈來輕松改進：
- 當
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("%lld\n", sum);
}
這個簡單的更改大大減少了運行時間！2000000比它快1000 倍以上：
chqrlie> time ./primesum
142913828922
real 0m0.288s
user 0m0.264s
sys 0m0.004s
但請注意，試除法的效率遠低于經典的 Eratosthenes 篩法。
這是一個簡單的版本：
#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("%lld\n", sum);
free(composite);
return 0;
}
對于 2000000，此代碼再快20 倍：
chqrlie> time ./primesum-sieve
142913828922
real 0m0.014s
user 0m0.007s
sys 0m0.002s
對于更大的邊界，可以通過多種方式進一步改進篩法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/447847.html