c - 如何优化下面的代码以确定低于 1,000,000,000 的素数的总数在 C 中它们的数字之和等于 14？

#include<stdio.h> #include<math.h> int main() { int i, j, count = 0, temp = 0, n, ans = 0, tot = 0; for (i = 1; i <= 1000000000; i++) { for (j = 2; j <= i / 2; j++) { if (i % j == 0) { count++; } } if (count == 0) { n = i; while (n != 0) { temp = n % 10; n = n / 10; ans = ans + temp; } if (ans == 14) { tot++; printf("%d,", i); } ans = 0; temp = 0; } count = 0; } // printf("%d:\n",tot); return 0; }

digit-sum 函数也可以使用提前返回，例如：

   int dsum14(int n) {
        int sum = 0;
        for (; n; n /= 10)
            if ((sum += n % 10) > 14)
                return 0;
        return sum == 14 ? 1 : 0;
    }

但是如何将（有效的）素数搜索和这个求和条件结合起来呢？

int n, cnt = 0;
for (n = 3; n < 1000*1000*1000; n += 2)
    if (n%3 && n%5 && dsum14(n) && n%7 && n%11 && n%13)
        cnt++;

这77469在 1.5 秒内给出。在dsum()逻辑链的任一端，它几乎是两倍。

该&& n%7 && n%11 && n%13部分将由使用最多约 32000（最大值的平方根）的素数列表的函数替换。

...或者您可以通过调整 digsum 函数将其优化为0.1 seconds 。

“只有” 575 个三位数字 000-999，总和为 14 或更少。所以我准备它们并将它们中的三个组合起来得到一个 9 位数字。生成它们而不是过滤它们。

尾巴看起来像：

920000021
920000201
920001011
920010011
920100011
920100101
920101001
921001001
931000001
total count: 22588

real    0m0.098s
user    0m0.100s
sys     0m0.002s

和开始：

不是 100% 确定它是否正确，但总数似乎也很合理。

这一切都依赖于给定的最大 1000 Mio。digsum_prime()使用它从三个（几乎）相等的部分构建候选编号。

代码：

#include <stdio.h>
#include <stdlib.h>

int parr[5000] = {3};

struct {
    int tri, sum;
} ts[999]; 

void primarr(void) {
    int maxn = 32000;
    int i = 1;
    for (int n = 5; n < maxn; n += 2)
        for (int div = 3;; div += 2) {
            if (!(n % div))
                break;
            if (div*div > n) {
                parr[i++] = n;
                break;
            }
        }    
}

int isprime(int n) {
    for(int i = 0;; i++) {
        if (!(n % parr[i]))
            return 0;
        if (parr[i]*parr[i] > n)
            return 1;
    }
}

int dsum(int n) {
    int sum = 0;
    for (; n; n /= 10) 
        sum += n % 10;
    return sum;
}
int tsarr(void) {
    int i = 0;
    for (int n = 0; n < 1000; n++) {
        int digsum = dsum(n);
        if (digsum <= 14) {
            ts[i].tri = n;
            ts[i].sum = digsum;
            i++;
        }
    }    
    return i;
}

int digsum_prime() {

    int cnt = 0;
    int tslen = tsarr();
    printf("tslen: %d\n", tslen);

    int high, mid, low;
    int sum, num;

    for (high = 0; high < tslen; high++) { 

        if(ts[high].sum > 13)
            continue;
        for (mid = 0; mid < tslen; mid++) { 

            if(ts[mid].sum + ts[high].sum > 13)
                continue;
            sum = ts[mid].sum + ts[high].sum;

            for (low = 0; low < tslen; low++)   
                if (ts[low].tri % 2) 
                    if(ts[low].sum + sum == 14) {

                        num = ts[high].tri * 1000*1000 
                            + ts[mid] .tri * 1000 
                            + ts[low] .tri;

                        if (isprime(num)) {
                            cnt++;        
                            printf("%d\n", num);
                        }
                    }
        }
    }
    
    return cnt; 
}

int main(void) {
    primarr();
    printf("total count: %d\n", digsum_prime());

}

将 13-13-14 更改为 3-3-4（但准备部分相同）给出了一个概览 - 在0.005秒内！

tslen: 575
13
31
103
211
1021
1201
2011
3001
10111
20011
20101
21001
100003
102001
1000003
1011001
1020001
1100101
2100001
10010101
10100011
20001001
30000001
101001001
200001001
total count: 25

real    0m0.005s
user    0m0.005s
sys     0m0.000s

确保执行时间为几秒钟。

哎呀

但是 OP 的限制是经过精心选择的：幼稚的方法需要几秒钟。

c - 如何优化下面的代码以确定低于 1,000,000,000 的素数的总数在 C 中它们的数字之和等于 14？

问题描述

解决方案

推荐阅读