承认自己很难得的开始对素数开始感兴趣了！！！

于是就在网上找各种关于素数的理论，还尼玛跑到亚马逊上买了本叫什么

 “ 对素数感兴趣的人们，费玛定理神码神马的。。。。。”

后来在 偶然进入Google treasure hunt之后

给我出了一道题是关于一个素数可以用那些连续的素数表示出来的问题，具体问题如下

Find the smallest number that can be expressed as

    the sum of 19 consecutive prime numbers,

    the sum of 21 consecutive prime numbers,

    the sum of 405 consecutive prime numbers,

    the sum of 781 consecutive prime numbers,

    and is itself a prime number.
For example, 41 is the smallest prime number that can be expressed as

the sum of 3 consecutive primes (11 + 13 + 17 = 41) and

the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).

让我来找这个最小的素数

自己不知道为什么特想知道这题的解题方法，因为很明显

这道题在让人思考怎样从庞大的数据种找到自己需要的东西，

于是就被吸引住了，如果有那位高人指点一下迷津，不慎感激，把我四分之三的分送出去

顶贴！！！

没看懂 5=2+3 两个连续的素数和还是一个素数 这个算最小么

难

————


[ 本帖最后由 有容就大 于 2012-6-18 12:03 编辑 ]

找到最小的数，可表示为19个连续质数的总和，21个连续质数的总和，405个连续质数的总和，781个连续质数的总和，和本身是一个素数。例如，41是最小的质数可以表示为3个连续质数之和（11 +13 +17 =41）和6个连续质数之和（2 +3 +5 +7 +11 +13 =41）。

恩，比如2，3，5，7就是连续4个素数
17就可以用上面这四个素数表示
然后看17还可不可以用其他的连续素数表示

多谢仁兄关注，其实我倒是挺想和大家一起讨论一下关于质数的各种各种各种的，虽然自己懂得也不多

问题还是归结到素数的寻找上。筛法虽然很快，但空间消耗太大。这里换一个折衷的方法。计算前一百万个素数大约需要4秒的时间。

#include<stdio.h>
#include<math.h>

#define    LENGTH_MAX    1000000

int prime[LENGTH_MAX] = {2, 3};

void init()
{
    int i, j, k, q;
    for(i = 2; i < LENGTH_MAX; prime[i++] = j)
    for(j = prime[i - 1] + 2;; j += 2)
    {
        for(q = sqrt(j), k = 1; prime[k] <= q && j % prime[k]; k++);
        if(prime[k] > q) break;
    }
}

int is_prime(int a)
{
    int from, to, p;
    for(from = 0, to = LENGTH_MAX - 1; from <= to;)
    {
        p = (from + to) >> 1;
        if(prime[p] > a) to = p - 1;
        else if(prime[p] < a) from = p + 1;
        else return 1;
    }
    return 0;
}

int find(int len, int * from)
{
    int i, j, s;
    for(s = i = 0; i < len; s += prime[i++]);
    if(!(len & 1))
        if(is_prime(s)){ *from = 0; return s;} else return 0;
    for(; i < LENGTH_MAX && !is_prime(s); i++)
        s += prime[i] - prime[i - len];
    if(i >= LENGTH_MAX) return 0;
    *from = i - len;
    return s;
}

int main()
{
    int i, from, s, len;
    printf("init...\n");
    init();
    printf("init over.\n");
    while(printf("input len : "), scanf("%d", &len), len < 1)
    {
        if(s = find(len, &from))
        {
            printf("%d", prime[from]);
            for(i = 1; i < len; printf(" + %d", prime[from + i++]));
            printf(" = %d\n", s);
        }
        else printf("no match.\n");
    }
    return 0;
}

因为输出太多，这里只附前三个的输出。
init...
init over.
input len : 19
11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 +
73 + 79 + 83 = 857
input len : 21
7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 7
1 + 73 + 79 + 83 + 89 = 953
input len : 405
19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 83 +
89 + 97 + 101 + 103 + 107 + 109 + 113 + 127 + 131 + 137 + 139 + 149 + 151 + 157
+ 163 + 167 + 173 + 179 + 181 + 191 + 193 + 197 + 199 + 211 + 223 + 227 + 229 +
233 + 239 + 241 + 251 + 257 + 263 + 269 + 271 + 277 + 281 + 283 + 293 + 307 + 31
1 + 313 + 317 + 331 + 337 + 347 + 349 + 353 + 359 + 367 + 373 + 379 + 383 + 389
+ 397 + 401 + 409 + 419 + 421 + 431 + 433 + 439 + 443 + 449 + 457 + 461 + 463 +
467 + 479 + 487 + 491 + 499 + 503 + 509 + 521 + 523 + 541 + 547 + 557 + 563 + 56
9 + 571 + 577 + 587 + 593 + 599 + 601 + 607 + 613 + 617 + 619 + 631 + 641 + 643
+ 647 + 653 + 659 + 661 + 673 + 677 + 683 + 691 + 701 + 709 + 719 + 727 + 733 +
739 + 743 + 751 + 757 + 761 + 769 + 773 + 787 + 797 + 809 + 811 + 821 + 823 + 82
7 + 829 + 839 + 853 + 857 + 859 + 863 + 877 + 881 + 883 + 887 + 907 + 911 + 919
+ 929 + 937 + 941 + 947 + 953 + 967 + 971 + 977 + 983 + 991 + 997 + 1009 + 1013
+ 1019 + 1021 + 1031 + 1033 + 1039 + 1049 + 1051 + 1061 + 1063 + 1069 + 1087 + 1
091 + 1093 + 1097 + 1103 + 1109 + 1117 + 1123 + 1129 + 1151 + 1153 + 1163 + 1171
 + 1181 + 1187 + 1193 + 1201 + 1213 + 1217 + 1223 + 1229 + 1231 + 1237 + 1249 +
1259 + 1277 + 1279 + 1283 + 1289 + 1291 + 1297 + 1301 + 1303 + 1307 + 1319 + 132
1 + 1327 + 1361 + 1367 + 1373 + 1381 + 1399 + 1409 + 1423 + 1427 + 1429 + 1433 +
 1439 + 1447 + 1451 + 1453 + 1459 + 1471 + 1481 + 1483 + 1487 + 1489 + 1493 + 14
99 + 1511 + 1523 + 1531 + 1543 + 1549 + 1553 + 1559 + 1567 + 1571 + 1579 + 1583
+ 1597 + 1601 + 1607 + 1609 + 1613 + 1619 + 1621 + 1627 + 1637 + 1657 + 1663 + 1
667 + 1669 + 1693 + 1697 + 1699 + 1709 + 1721 + 1723 + 1733 + 1741 + 1747 + 1753
 + 1759 + 1777 + 1783 + 1787 + 1789 + 1801 + 1811 + 1823 + 1831 + 1847 + 1861 +
1867 + 1871 + 1873 + 1877 + 1879 + 1889 + 1901 + 1907 + 1913 + 1931 + 1933 + 194
9 + 1951 + 1973 + 1979 + 1987 + 1993 + 1997 + 1999 + 2003 + 2011 + 2017 + 2027 +
 2029 + 2039 + 2053 + 2063 + 2069 + 2081 + 2083 + 2087 + 2089 + 2099 + 2111 + 21
13 + 2129 + 2131 + 2137 + 2141 + 2143 + 2153 + 2161 + 2179 + 2203 + 2207 + 2213
+ 2221 + 2237 + 2239 + 2243 + 2251 + 2267 + 2269 + 2273 + 2281 + 2287 + 2293 + 2
297 + 2309 + 2311 + 2333 + 2339 + 2341 + 2347 + 2351 + 2357 + 2371 + 2377 + 2381
 + 2383 + 2389 + 2393 + 2399 + 2411 + 2417 + 2423 + 2437 + 2441 + 2447 + 2459 +
2467 + 2473 + 2477 + 2503 + 2521 + 2531 + 2539 + 2543 + 2549 + 2551 + 2557 + 257
9 + 2591 + 2593 + 2609 + 2617 + 2621 + 2633 + 2647 + 2657 + 2659 + 2663 + 2671 +
 2677 + 2683 + 2687 + 2689 + 2693 + 2699 + 2707 + 2711 + 2713 + 2719 + 2729 + 27
31 + 2741 + 2749 + 2753 + 2767 + 2777 + 2789 + 2791 + 2797 + 2801 + 2803 + 2819
+ 2833 + 2837 = 541283

呵呵 这个方法其实比较简单 就是搜索的数太多 要有一个比较好节约时间的方法才行，不然要等好久好久。
看了看网上的这方面的东西， 有的要求比你的还夸张， 连续的1024个素数之和 呵呵
貌似用到文件保存素数表 刚开始我以为简单 写了个 发现不对 后来改了下 直接搜 那叫一个耗费时间
期待更好的方法。