1 /****************************************************************************
3 * Copyright (C) 2006-2009 Sourcefire, Inc.
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License Version 2 as
7 * published by the Free Software Foundation. You may not use, modify or
8 * distribute this program under any other version of the GNU General
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 ****************************************************************************/
25 * Prime number calculation via Table lookups.
27 * This was implemented for use with the hasing functions
28 * in sfghash, and sfxhash.
31 #include "sfprimetable.h"
32 /* 0-8K, increments=8 */
34 unsigned prime_table0
[1024]={
1060 /* 0-64K, increments=64 */
1062 unsigned prime_table1
[]={
2088 /* 0-1M, increments=1024 */
2090 unsigned prime_table2
[1024]={
2188 100343, /* 100352 */
2189 101363, /* 101376 */
2190 102397, /* 102400 */
2191 103423, /* 103424 */
2192 104417, /* 104448 */
2193 105467, /* 105472 */
2194 106487, /* 106496 */
2195 107509, /* 107520 */
2196 108541, /* 108544 */
2197 109567, /* 109568 */
2198 110587, /* 110592 */
2199 111611, /* 111616 */
2200 112621, /* 112640 */
2201 113657, /* 113664 */
2202 114679, /* 114688 */
2203 115693, /* 115712 */
2204 116731, /* 116736 */
2205 117757, /* 117760 */
2206 118757, /* 118784 */
2207 119797, /* 119808 */
2208 120829, /* 120832 */
2209 121853, /* 121856 */
2210 122869, /* 122880 */
2211 123887, /* 123904 */
2212 124919, /* 124928 */
2213 125941, /* 125952 */
2214 126967, /* 126976 */
2215 127997, /* 128000 */
2216 129023, /* 129024 */
2217 130043, /* 130048 */
2218 131071, /* 131072 */
2219 132071, /* 132096 */
2220 133117, /* 133120 */
2221 134129, /* 134144 */
2222 135151, /* 135168 */
2223 136189, /* 136192 */
2224 137209, /* 137216 */
2225 138239, /* 138240 */
2226 139241, /* 139264 */
2227 140281, /* 140288 */
2228 141311, /* 141312 */
2229 142327, /* 142336 */
2230 143357, /* 143360 */
2231 144383, /* 144384 */
2232 145399, /* 145408 */
2233 146423, /* 146432 */
2234 147451, /* 147456 */
2235 148471, /* 148480 */
2236 149503, /* 149504 */
2237 150523, /* 150528 */
2238 151549, /* 151552 */
2239 152567, /* 152576 */
2240 153589, /* 153600 */
2241 154621, /* 154624 */
2242 155627, /* 155648 */
2243 156671, /* 156672 */
2244 157679, /* 157696 */
2245 158699, /* 158720 */
2246 159739, /* 159744 */
2247 160757, /* 160768 */
2248 161783, /* 161792 */
2249 162791, /* 162816 */
2250 163819, /* 163840 */
2251 164839, /* 164864 */
2252 165887, /* 165888 */
2253 166909, /* 166912 */
2254 167917, /* 167936 */
2255 168943, /* 168960 */
2256 169957, /* 169984 */
2257 171007, /* 171008 */
2258 172031, /* 172032 */
2259 173053, /* 173056 */
2260 174079, /* 174080 */
2261 175103, /* 175104 */
2262 176123, /* 176128 */
2263 177131, /* 177152 */
2264 178169, /* 178176 */
2265 179173, /* 179200 */
2266 180221, /* 180224 */
2267 181243, /* 181248 */
2268 182261, /* 182272 */
2269 183289, /* 183296 */
2270 184309, /* 184320 */
2271 185327, /* 185344 */
2272 186343, /* 186368 */
2273 187387, /* 187392 */
2274 188407, /* 188416 */
2275 189439, /* 189440 */
2276 190409, /* 190464 */
2277 191473, /* 191488 */
2278 192499, /* 192512 */
2279 193513, /* 193536 */
2280 194543, /* 194560 */
2281 195581, /* 195584 */
2282 196597, /* 196608 */
2283 197621, /* 197632 */
2284 198647, /* 198656 */
2285 199679, /* 199680 */
2286 200699, /* 200704 */
2287 201709, /* 201728 */
2288 202751, /* 202752 */
2289 203773, /* 203776 */
2290 204797, /* 204800 */
2291 205823, /* 205824 */
2292 206827, /* 206848 */
2293 207869, /* 207872 */
2294 208891, /* 208896 */
2295 209917, /* 209920 */
2296 210943, /* 210944 */
2297 211949, /* 211968 */
2298 212987, /* 212992 */
2299 214009, /* 214016 */
2300 214993, /* 215040 */
2301 216061, /* 216064 */
2302 217081, /* 217088 */
2303 218111, /* 218112 */
2304 219133, /* 219136 */
2305 220151, /* 220160 */
2306 221173, /* 221184 */
2307 222199, /* 222208 */
2308 223229, /* 223232 */
2309 224251, /* 224256 */
2310 225263, /* 225280 */
2311 226283, /* 226304 */
2312 227303, /* 227328 */
2313 228341, /* 228352 */
2314 229373, /* 229376 */
2315 230393, /* 230400 */
2316 231419, /* 231424 */
2317 232439, /* 232448 */
2318 233437, /* 233472 */
2319 234473, /* 234496 */
2320 235519, /* 235520 */
2321 236527, /* 236544 */
2322 237563, /* 237568 */
2323 238591, /* 238592 */
2324 239611, /* 239616 */
2325 240631, /* 240640 */
2326 241663, /* 241664 */
2327 242681, /* 242688 */
2328 243709, /* 243712 */
2329 244733, /* 244736 */
2330 245759, /* 245760 */
2331 246781, /* 246784 */
2332 247799, /* 247808 */
2333 248827, /* 248832 */
2334 249853, /* 249856 */
2335 250871, /* 250880 */
2336 251903, /* 251904 */
2337 252919, /* 252928 */
2338 253951, /* 253952 */
2339 254971, /* 254976 */
2340 255989, /* 256000 */
2341 257017, /* 257024 */
2342 258031, /* 258048 */
2343 259033, /* 259072 */
2344 260089, /* 260096 */
2345 261101, /* 261120 */
2346 262139, /* 262144 */
2347 263167, /* 263168 */
2348 264179, /* 264192 */
2349 265207, /* 265216 */
2350 266239, /* 266240 */
2351 267259, /* 267264 */
2352 268283, /* 268288 */
2353 269281, /* 269312 */
2354 270329, /* 270336 */
2355 271357, /* 271360 */
2356 272383, /* 272384 */
2357 273367, /* 273408 */
2358 274423, /* 274432 */
2359 275453, /* 275456 */
2360 276467, /* 276480 */
2361 277499, /* 277504 */
2362 278503, /* 278528 */
2363 279551, /* 279552 */
2364 280561, /* 280576 */
2365 281581, /* 281600 */
2366 282617, /* 282624 */
2367 283639, /* 283648 */
2368 284659, /* 284672 */
2369 285673, /* 285696 */
2370 286711, /* 286720 */
2371 287731, /* 287744 */
2372 288767, /* 288768 */
2373 289789, /* 289792 */
2374 290803, /* 290816 */
2375 291833, /* 291840 */
2376 292849, /* 292864 */
2377 293863, /* 293888 */
2378 294911, /* 294912 */
2379 295909, /* 295936 */
2380 296941, /* 296960 */
2381 297971, /* 297984 */
2382 298999, /* 299008 */
2383 300023, /* 300032 */
2384 301051, /* 301056 */
2385 302053, /* 302080 */
2386 303097, /* 303104 */
2387 304127, /* 304128 */
2388 305147, /* 305152 */
2389 306169, /* 306176 */
2390 307189, /* 307200 */
2391 308219, /* 308224 */
2392 309241, /* 309248 */
2393 310243, /* 310272 */
2394 311293, /* 311296 */
2395 312313, /* 312320 */
2396 313343, /* 313344 */
2397 314359, /* 314368 */
2398 315389, /* 315392 */
2399 316403, /* 316416 */
2400 317437, /* 317440 */
2401 318457, /* 318464 */
2402 319483, /* 319488 */
2403 320483, /* 320512 */
2404 321509, /* 321536 */
2405 322559, /* 322560 */
2406 323581, /* 323584 */
2407 324593, /* 324608 */
2408 325631, /* 325632 */
2409 326633, /* 326656 */
2410 327673, /* 327680 */
2411 328687, /* 328704 */
2412 329723, /* 329728 */
2413 330749, /* 330752 */
2414 331769, /* 331776 */
2415 332791, /* 332800 */
2416 333821, /* 333824 */
2417 334843, /* 334848 */
2418 335857, /* 335872 */
2419 336887, /* 336896 */
2420 337919, /* 337920 */
2421 338927, /* 338944 */
2422 339959, /* 339968 */
2423 340979, /* 340992 */
2424 341993, /* 342016 */
2425 343037, /* 343040 */
2426 344053, /* 344064 */
2427 345067, /* 345088 */
2428 346111, /* 346112 */
2429 347131, /* 347136 */
2430 348149, /* 348160 */
2431 349183, /* 349184 */
2432 350191, /* 350208 */
2433 351229, /* 351232 */
2434 352249, /* 352256 */
2435 353263, /* 353280 */
2436 354301, /* 354304 */
2437 355321, /* 355328 */
2438 356351, /* 356352 */
2439 357359, /* 357376 */
2440 358373, /* 358400 */
2441 359419, /* 359424 */
2442 360439, /* 360448 */
2443 361469, /* 361472 */
2444 362473, /* 362496 */
2445 363497, /* 363520 */
2446 364543, /* 364544 */
2447 365567, /* 365568 */
2448 366547, /* 366592 */
2449 367613, /* 367616 */
2450 368633, /* 368640 */
2451 369661, /* 369664 */
2452 370687, /* 370688 */
2453 371699, /* 371712 */
2454 372733, /* 372736 */
2455 373757, /* 373760 */
2456 374783, /* 374784 */
2457 375799, /* 375808 */
2458 376823, /* 376832 */
2459 377851, /* 377856 */
2460 378869, /* 378880 */
2461 379903, /* 379904 */
2462 380917, /* 380928 */
2463 381949, /* 381952 */
2464 382961, /* 382976 */
2465 383987, /* 384000 */
2466 385013, /* 385024 */
2467 386047, /* 386048 */
2468 387071, /* 387072 */
2469 388081, /* 388096 */
2470 389117, /* 389120 */
2471 390119, /* 390144 */
2472 391163, /* 391168 */
2473 392177, /* 392192 */
2474 393209, /* 393216 */
2475 394223, /* 394240 */
2476 395261, /* 395264 */
2477 396269, /* 396288 */
2478 397303, /* 397312 */
2479 398323, /* 398336 */
2480 399353, /* 399360 */
2481 400381, /* 400384 */
2482 401407, /* 401408 */
2483 402419, /* 402432 */
2484 403439, /* 403456 */
2485 404461, /* 404480 */
2486 405499, /* 405504 */
2487 406517, /* 406528 */
2488 407527, /* 407552 */
2489 408563, /* 408576 */
2490 409597, /* 409600 */
2491 410623, /* 410624 */
2492 411641, /* 411648 */
2493 412667, /* 412672 */
2494 413689, /* 413696 */
2495 414709, /* 414720 */
2496 415729, /* 415744 */
2497 416761, /* 416768 */
2498 417773, /* 417792 */
2499 418813, /* 418816 */
2500 419831, /* 419840 */
2501 420859, /* 420864 */
2502 421847, /* 421888 */
2503 422911, /* 422912 */
2504 423931, /* 423936 */
2505 424939, /* 424960 */
2506 425977, /* 425984 */
2507 427001, /* 427008 */
2508 428027, /* 428032 */
2509 429043, /* 429056 */
2510 430061, /* 430080 */
2511 431099, /* 431104 */
2512 432121, /* 432128 */
2513 433151, /* 433152 */
2514 434167, /* 434176 */
2515 435191, /* 435200 */
2516 436217, /* 436224 */
2517 437243, /* 437248 */
2518 438271, /* 438272 */
2519 439289, /* 439296 */
2520 440311, /* 440320 */
2521 441319, /* 441344 */
2522 442367, /* 442368 */
2523 443389, /* 443392 */
2524 444403, /* 444416 */
2525 445433, /* 445440 */
2526 446461, /* 446464 */
2527 447481, /* 447488 */
2528 448451, /* 448512 */
2529 449473, /* 449536 */
2530 450557, /* 450560 */
2531 451579, /* 451584 */
2532 452597, /* 452608 */
2533 453631, /* 453632 */
2534 454637, /* 454656 */
2535 455659, /* 455680 */
2536 456697, /* 456704 */
2537 457711, /* 457728 */
2538 458747, /* 458752 */
2539 459763, /* 459776 */
2540 460793, /* 460800 */
2541 461819, /* 461824 */
2542 462841, /* 462848 */
2543 463867, /* 463872 */
2544 464879, /* 464896 */
2545 465917, /* 465920 */
2546 466919, /* 466944 */
2547 467963, /* 467968 */
2548 468983, /* 468992 */
2549 469993, /* 470016 */
2550 471007, /* 471040 */
2551 472063, /* 472064 */
2552 473027, /* 473088 */
2553 474101, /* 474112 */
2554 475109, /* 475136 */
2555 476143, /* 476160 */
2556 477163, /* 477184 */
2557 478207, /* 478208 */
2558 479231, /* 479232 */
2559 480209, /* 480256 */
2560 481249, /* 481280 */
2561 482281, /* 482304 */
2562 483323, /* 483328 */
2563 484339, /* 484352 */
2564 485371, /* 485376 */
2565 486397, /* 486400 */
2566 487423, /* 487424 */
2567 488441, /* 488448 */
2568 489457, /* 489472 */
2569 490493, /* 490496 */
2570 491503, /* 491520 */
2571 492523, /* 492544 */
2572 493567, /* 493568 */
2573 494591, /* 494592 */
2574 495613, /* 495616 */
2575 496631, /* 496640 */
2576 497663, /* 497664 */
2577 498679, /* 498688 */
2578 499711, /* 499712 */
2579 500729, /* 500736 */
2580 501731, /* 501760 */
2581 502781, /* 502784 */
2582 503803, /* 503808 */
2583 504821, /* 504832 */
2584 505823, /* 505856 */
2585 506873, /* 506880 */
2586 507901, /* 507904 */
2587 508919, /* 508928 */
2588 509947, /* 509952 */
2589 510943, /* 510976 */
2590 511997, /* 512000 */
2591 513017, /* 513024 */
2592 514021, /* 514048 */
2593 515041, /* 515072 */
2594 516091, /* 516096 */
2595 517091, /* 517120 */
2596 518137, /* 518144 */
2597 519161, /* 519168 */
2598 520151, /* 520192 */
2599 521201, /* 521216 */
2600 522239, /* 522240 */
2601 523261, /* 523264 */
2602 524287, /* 524288 */
2603 525299, /* 525312 */
2604 526307, /* 526336 */
2605 527353, /* 527360 */
2606 528383, /* 528384 */
2607 529393, /* 529408 */
2608 530429, /* 530432 */
2609 531383, /* 531456 */
2610 532453, /* 532480 */
2611 533459, /* 533504 */
2612 534511, /* 534528 */
2613 535547, /* 535552 */
2614 536563, /* 536576 */
2615 537599, /* 537600 */
2616 538621, /* 538624 */
2617 539641, /* 539648 */
2618 540629, /* 540672 */
2619 541693, /* 541696 */
2620 542719, /* 542720 */
2621 543713, /* 543744 */
2622 544759, /* 544768 */
2623 545791, /* 545792 */
2624 546781, /* 546816 */
2625 547831, /* 547840 */
2626 548861, /* 548864 */
2627 549883, /* 549888 */
2628 550909, /* 550912 */
2629 551933, /* 551936 */
2630 552917, /* 552960 */
2631 553981, /* 553984 */
2632 554977, /* 555008 */
2633 556027, /* 556032 */
2634 557041, /* 557056 */
2635 558067, /* 558080 */
2636 559099, /* 559104 */
2637 560123, /* 560128 */
2638 561109, /* 561152 */
2639 562169, /* 562176 */
2640 563197, /* 563200 */
2641 564197, /* 564224 */
2642 565247, /* 565248 */
2643 566233, /* 566272 */
2644 567277, /* 567296 */
2645 568303, /* 568320 */
2646 569323, /* 569344 */
2647 570359, /* 570368 */
2648 571381, /* 571392 */
2649 572399, /* 572416 */
2650 573437, /* 573440 */
2651 574439, /* 574464 */
2652 575479, /* 575488 */
2653 576509, /* 576512 */
2654 577531, /* 577536 */
2655 578537, /* 578560 */
2656 579583, /* 579584 */
2657 580607, /* 580608 */
2658 581617, /* 581632 */
2659 582649, /* 582656 */
2660 583673, /* 583680 */
2661 584699, /* 584704 */
2662 585727, /* 585728 */
2663 586741, /* 586752 */
2664 587773, /* 587776 */
2665 588779, /* 588800 */
2666 589811, /* 589824 */
2667 590839, /* 590848 */
2668 591863, /* 591872 */
2669 592877, /* 592896 */
2670 593903, /* 593920 */
2671 594931, /* 594944 */
2672 595967, /* 595968 */
2673 596987, /* 596992 */
2674 598007, /* 598016 */
2675 599023, /* 599040 */
2676 600053, /* 600064 */
2677 601079, /* 601088 */
2678 602111, /* 602112 */
2679 603133, /* 603136 */
2680 604073, /* 604160 */
2681 605177, /* 605184 */
2682 606181, /* 606208 */
2683 607219, /* 607232 */
2684 608213, /* 608256 */
2685 609277, /* 609280 */
2686 610301, /* 610304 */
2687 611323, /* 611328 */
2688 612349, /* 612352 */
2689 613367, /* 613376 */
2690 614387, /* 614400 */
2691 615413, /* 615424 */
2692 616439, /* 616448 */
2693 617471, /* 617472 */
2694 618463, /* 618496 */
2695 619511, /* 619520 */
2696 620531, /* 620544 */
2697 621541, /* 621568 */
2698 622577, /* 622592 */
2699 623591, /* 623616 */
2700 624607, /* 624640 */
2701 625663, /* 625664 */
2702 626687, /* 626688 */
2703 627709, /* 627712 */
2704 628721, /* 628736 */
2705 629747, /* 629760 */
2706 630737, /* 630784 */
2707 631789, /* 631808 */
2708 632813, /* 632832 */
2709 633833, /* 633856 */
2710 634871, /* 634880 */
2711 635893, /* 635904 */
2712 636919, /* 636928 */
2713 637939, /* 637952 */
2714 638971, /* 638976 */
2715 639997, /* 640000 */
2716 640993, /* 641024 */
2717 642013, /* 642048 */
2718 643061, /* 643072 */
2719 644089, /* 644096 */
2720 645097, /* 645120 */
2721 646103, /* 646144 */
2722 647161, /* 647168 */
2723 648191, /* 648192 */
2724 649183, /* 649216 */
2725 650227, /* 650240 */
2726 651257, /* 651264 */
2727 652283, /* 652288 */
2728 653311, /* 653312 */
2729 654323, /* 654336 */
2730 655357, /* 655360 */
2731 656377, /* 656384 */
2732 657403, /* 657408 */
2733 658417, /* 658432 */
2734 659453, /* 659456 */
2735 660449, /* 660480 */
2736 661483, /* 661504 */
2737 662527, /* 662528 */
2738 663547, /* 663552 */
2739 664571, /* 664576 */
2740 665591, /* 665600 */
2741 666607, /* 666624 */
2742 667643, /* 667648 */
2743 668671, /* 668672 */
2744 669689, /* 669696 */
2745 670711, /* 670720 */
2746 671743, /* 671744 */
2747 672767, /* 672768 */
2748 673787, /* 673792 */
2749 674813, /* 674816 */
2750 675839, /* 675840 */
2751 676861, /* 676864 */
2752 677857, /* 677888 */
2753 678907, /* 678912 */
2754 679933, /* 679936 */
2755 680959, /* 680960 */
2756 681983, /* 681984 */
2757 683003, /* 683008 */
2758 684017, /* 684032 */
2759 685051, /* 685056 */
2760 686057, /* 686080 */
2761 687101, /* 687104 */
2762 688111, /* 688128 */
2763 689141, /* 689152 */
2764 690163, /* 690176 */
2765 691199, /* 691200 */
2766 692221, /* 692224 */
2767 693223, /* 693248 */
2768 694271, /* 694272 */
2769 695293, /* 695296 */
2770 696317, /* 696320 */
2771 697327, /* 697344 */
2772 698359, /* 698368 */
2773 699383, /* 699392 */
2774 700393, /* 700416 */
2775 701419, /* 701440 */
2776 702451, /* 702464 */
2777 703471, /* 703488 */
2778 704507, /* 704512 */
2779 705533, /* 705536 */
2780 706547, /* 706560 */
2781 707573, /* 707584 */
2782 708601, /* 708608 */
2783 709609, /* 709632 */
2784 710641, /* 710656 */
2785 711679, /* 711680 */
2786 712697, /* 712704 */
2787 713681, /* 713728 */
2788 714751, /* 714752 */
2789 715753, /* 715776 */
2790 716789, /* 716800 */
2791 717817, /* 717824 */
2792 718847, /* 718848 */
2793 719839, /* 719872 */
2794 720887, /* 720896 */
2795 721909, /* 721920 */
2796 722933, /* 722944 */
2797 723967, /* 723968 */
2798 724991, /* 724992 */
2799 726013, /* 726016 */
2800 727021, /* 727040 */
2801 728047, /* 728064 */
2802 729073, /* 729088 */
2803 730111, /* 730112 */
2804 731117, /* 731136 */
2805 732157, /* 732160 */
2806 733177, /* 733184 */
2807 734207, /* 734208 */
2808 735211, /* 735232 */
2809 736249, /* 736256 */
2810 737279, /* 737280 */
2811 738301, /* 738304 */
2812 739327, /* 739328 */
2813 740351, /* 740352 */
2814 741373, /* 741376 */
2815 742393, /* 742400 */
2816 743423, /* 743424 */
2817 744431, /* 744448 */
2818 745471, /* 745472 */
2819 746483, /* 746496 */
2820 747499, /* 747520 */
2821 748541, /* 748544 */
2822 749557, /* 749568 */
2823 750571, /* 750592 */
2824 751613, /* 751616 */
2825 752639, /* 752640 */
2826 753659, /* 753664 */
2827 754651, /* 754688 */
2828 755707, /* 755712 */
2829 756727, /* 756736 */
2830 757753, /* 757760 */
2831 758783, /* 758784 */
2832 759799, /* 759808 */
2833 760813, /* 760832 */
2834 761833, /* 761856 */
2835 762877, /* 762880 */
2836 763901, /* 763904 */
2837 764903, /* 764928 */
2838 765949, /* 765952 */
2839 766967, /* 766976 */
2840 767957, /* 768000 */
2841 769019, /* 769024 */
2842 770047, /* 770048 */
2843 771049, /* 771072 */
2844 772091, /* 772096 */
2845 773117, /* 773120 */
2846 774143, /* 774144 */
2847 775163, /* 775168 */
2848 776183, /* 776192 */
2849 777209, /* 777216 */
2850 778237, /* 778240 */
2851 779249, /* 779264 */
2852 780287, /* 780288 */
2853 781309, /* 781312 */
2854 782329, /* 782336 */
2855 783359, /* 783360 */
2856 784379, /* 784384 */
2857 785377, /* 785408 */
2858 786431, /* 786432 */
2859 787447, /* 787456 */
2860 788479, /* 788480 */
2861 789493, /* 789504 */
2862 790523, /* 790528 */
2863 791543, /* 791552 */
2864 792563, /* 792576 */
2865 793591, /* 793600 */
2866 794593, /* 794624 */
2867 795647, /* 795648 */
2868 796657, /* 796672 */
2869 797689, /* 797696 */
2870 798713, /* 798720 */
2871 799741, /* 799744 */
2872 800759, /* 800768 */
2873 801791, /* 801792 */
2874 802811, /* 802816 */
2875 803819, /* 803840 */
2876 804857, /* 804864 */
2877 805877, /* 805888 */
2878 806903, /* 806912 */
2879 807931, /* 807936 */
2880 808957, /* 808960 */
2881 809983, /* 809984 */
2882 810989, /* 811008 */
2883 812011, /* 812032 */
2884 813049, /* 813056 */
2885 814069, /* 814080 */
2886 815063, /* 815104 */
2887 816121, /* 816128 */
2888 817151, /* 817152 */
2889 818173, /* 818176 */
2890 819187, /* 819200 */
2891 820223, /* 820224 */
2892 821209, /* 821248 */
2893 822259, /* 822272 */
2894 823283, /* 823296 */
2895 824287, /* 824320 */
2896 825343, /* 825344 */
2897 826363, /* 826368 */
2898 827389, /* 827392 */
2899 828409, /* 828416 */
2900 829399, /* 829440 */
2901 830449, /* 830464 */
2902 831461, /* 831488 */
2903 832499, /* 832512 */
2904 833509, /* 833536 */
2905 834527, /* 834560 */
2906 835559, /* 835584 */
2907 836573, /* 836608 */
2908 837631, /* 837632 */
2909 838633, /* 838656 */
2910 839669, /* 839680 */
2911 840703, /* 840704 */
2912 841727, /* 841728 */
2913 842747, /* 842752 */
2914 843763, /* 843776 */
2915 844777, /* 844800 */
2916 845809, /* 845824 */
2917 846841, /* 846848 */
2918 847871, /* 847872 */
2919 848893, /* 848896 */
2920 849917, /* 849920 */
2921 850943, /* 850944 */
2922 851957, /* 851968 */
2923 852989, /* 852992 */
2924 853999, /* 854016 */
2925 855031, /* 855040 */
2926 856061, /* 856064 */
2927 857083, /* 857088 */
2928 858103, /* 858112 */
2929 859121, /* 859136 */
2930 860143, /* 860160 */
2931 861167, /* 861184 */
2932 862207, /* 862208 */
2933 863231, /* 863232 */
2934 864251, /* 864256 */
2935 865261, /* 865280 */
2936 866293, /* 866304 */
2937 867319, /* 867328 */
2938 868349, /* 868352 */
2939 869371, /* 869376 */
2940 870391, /* 870400 */
2941 871393, /* 871424 */
2942 872441, /* 872448 */
2943 873469, /* 873472 */
2944 874487, /* 874496 */
2945 875519, /* 875520 */
2946 876529, /* 876544 */
2947 877567, /* 877568 */
2948 878573, /* 878592 */
2949 879607, /* 879616 */
2950 880603, /* 880640 */
2951 881663, /* 881664 */
2952 882659, /* 882688 */
2953 883703, /* 883712 */
2954 884717, /* 884736 */
2955 885737, /* 885760 */
2956 886777, /* 886784 */
2957 887759, /* 887808 */
2958 888827, /* 888832 */
2959 889829, /* 889856 */
2960 890867, /* 890880 */
2961 891899, /* 891904 */
2962 892919, /* 892928 */
2963 893939, /* 893952 */
2964 894973, /* 894976 */
2965 895987, /* 896000 */
2966 897019, /* 897024 */
2967 898033, /* 898048 */
2968 899069, /* 899072 */
2969 900091, /* 900096 */
2970 901111, /* 901120 */
2971 902141, /* 902144 */
2972 903163, /* 903168 */
2973 904181, /* 904192 */
2974 905213, /* 905216 */
2975 906233, /* 906240 */
2976 907259, /* 907264 */
2977 908287, /* 908288 */
2978 909301, /* 909312 */
2979 910307, /* 910336 */
2980 911359, /* 911360 */
2981 912367, /* 912384 */
2982 913397, /* 913408 */
2983 914429, /* 914432 */
2984 915451, /* 915456 */
2985 916477, /* 916480 */
2986 917503, /* 917504 */
2987 918497, /* 918528 */
2988 919531, /* 919552 */
2989 920561, /* 920576 */
2990 921589, /* 921600 */
2991 922619, /* 922624 */
2992 923641, /* 923648 */
2993 924661, /* 924672 */
2994 925679, /* 925696 */
2995 926707, /* 926720 */
2996 927743, /* 927744 */
2997 928703, /* 928768 */
2998 929791, /* 929792 */
2999 930779, /* 930816 */
3000 931837, /* 931840 */
3001 932863, /* 932864 */
3002 933883, /* 933888 */
3003 934909, /* 934912 */
3004 935903, /* 935936 */
3005 936953, /* 936960 */
3006 937969, /* 937984 */
3007 939007, /* 939008 */
3008 940031, /* 940032 */
3009 941041, /* 941056 */
3010 942079, /* 942080 */
3011 943097, /* 943104 */
3012 944123, /* 944128 */
3013 945151, /* 945152 */
3014 946163, /* 946176 */
3015 947197, /* 947200 */
3016 948187, /* 948224 */
3017 949243, /* 949248 */
3018 950269, /* 950272 */
3019 951283, /* 951296 */
3020 952313, /* 952320 */
3021 953341, /* 953344 */
3022 954367, /* 954368 */
3023 955391, /* 955392 */
3024 956401, /* 956416 */
3025 957433, /* 957440 */
3026 958459, /* 958464 */
3027 959479, /* 959488 */
3028 960499, /* 960512 */
3029 961531, /* 961536 */
3030 962543, /* 962560 */
3031 963581, /* 963584 */
3032 964589, /* 964608 */
3033 965623, /* 965632 */
3034 966653, /* 966656 */
3035 967667, /* 967680 */
3036 968699, /* 968704 */
3037 969721, /* 969728 */
3038 970747, /* 970752 */
3039 971767, /* 971776 */
3040 972799, /* 972800 */
3041 973823, /* 973824 */
3042 974837, /* 974848 */
3043 975869, /* 975872 */
3044 976883, /* 976896 */
3045 977897, /* 977920 */
3046 978931, /* 978944 */
3047 979949, /* 979968 */
3048 980963, /* 980992 */
3049 981983, /* 982016 */
3050 982981, /* 983040 */
3051 984059, /* 984064 */
3052 985079, /* 985088 */
3053 986101, /* 986112 */
3054 987127, /* 987136 */
3055 988157, /* 988160 */
3056 989173, /* 989184 */
3057 990181, /* 990208 */
3058 991229, /* 991232 */
3059 992249, /* 992256 */
3060 993269, /* 993280 */
3061 994303, /* 994304 */
3062 995327, /* 995328 */
3063 996329, /* 996352 */
3064 997369, /* 997376 */
3065 998399, /* 998400 */
3066 999389, /* 999424 */
3067 1000429, /* 1000448 */
3068 1001467, /* 1001472 */
3069 1002493, /* 1002496 */
3070 1003517, /* 1003520 */
3071 1004537, /* 1004544 */
3072 1005553, /* 1005568 */
3073 1006589, /* 1006592 */
3074 1007609, /* 1007616 */
3075 1008617, /* 1008640 */
3076 1009651, /* 1009664 */
3077 1010687, /* 1010688 */
3078 1011697, /* 1011712 */
3079 1012733, /* 1012736 */
3080 1013741, /* 1013760 */
3081 1014779, /* 1014784 */
3082 1015769, /* 1015808 */
3083 1016789, /* 1016832 */
3084 1017851, /* 1017856 */
3085 1018879, /* 1018880 */
3086 1019903, /* 1019904 */
3087 1020913, /* 1020928 */
3088 1021919, /* 1021952 */
3089 1022963, /* 1022976 */
3090 1023991, /* 1024000 */
3091 1025021, /* 1025024 */
3092 1026043, /* 1026048 */
3093 1027067, /* 1027072 */
3094 1028089, /* 1028096 */
3095 1029113, /* 1029120 */
3096 1030121, /* 1030144 */
3097 1031161, /* 1031168 */
3098 1032191, /* 1032192 */
3099 1033189, /* 1033216 */
3100 1034239, /* 1034240 */
3101 1035263, /* 1035264 */
3102 1036271, /* 1036288 */
3103 1037303, /* 1037312 */
3104 1038329, /* 1038336 */
3105 1039351, /* 1039360 */
3106 1040381, /* 1040384 */
3107 1041373, /* 1041408 */
3108 1042427, /* 1042432 */
3109 1043453, /* 1043456 */
3110 1044479, /* 1044480 */
3111 1045493, /* 1045504 */
3112 1046527, /* 1046528 */
3113 1047551, /* 1047552 */
3115 /* 0-128M, increments=102400 */
3117 unsigned prime_table3
[1024]={
3118 131071, /* 131072 */
3119 262139, /* 262144 */
3120 393209, /* 393216 */
3121 524287, /* 524288 */
3122 655357, /* 655360 */
3123 786431, /* 786432 */
3124 917503, /* 917504 */
3125 1048573, /* 1048576 */
3126 1179641, /* 1179648 */
3127 1310719, /* 1310720 */
3128 1441771, /* 1441792 */
3129 1572853, /* 1572864 */
3130 1703903, /* 1703936 */
3131 1835003, /* 1835008 */
3132 1966079, /* 1966080 */
3133 2097143, /* 2097152 */
3134 2228221, /* 2228224 */
3135 2359267, /* 2359296 */
3136 2490337, /* 2490368 */
3137 2621431, /* 2621440 */
3138 2752499, /* 2752512 */
3139 2883577, /* 2883584 */
3140 3014653, /* 3014656 */
3141 3145721, /* 3145728 */
3142 3276799, /* 3276800 */
3143 3407857, /* 3407872 */
3144 3538933, /* 3538944 */
3145 3670013, /* 3670016 */
3146 3801073, /* 3801088 */
3147 3932153, /* 3932160 */
3148 4063217, /* 4063232 */
3149 4194301, /* 4194304 */
3150 4325359, /* 4325376 */
3151 4456433, /* 4456448 */
3152 4587503, /* 4587520 */
3153 4718579, /* 4718592 */
3154 4849651, /* 4849664 */
3155 4980727, /* 4980736 */
3156 5111791, /* 5111808 */
3157 5242877, /* 5242880 */
3158 5373931, /* 5373952 */
3159 5505023, /* 5505024 */
3160 5636077, /* 5636096 */
3161 5767129, /* 5767168 */
3162 5898209, /* 5898240 */
3163 6029299, /* 6029312 */
3164 6160381, /* 6160384 */
3165 6291449, /* 6291456 */
3166 6422519, /* 6422528 */
3167 6553577, /* 6553600 */
3168 6684659, /* 6684672 */
3169 6815741, /* 6815744 */
3170 6946813, /* 6946816 */
3171 7077883, /* 7077888 */
3172 7208951, /* 7208960 */
3173 7340009, /* 7340032 */
3174 7471099, /* 7471104 */
3175 7602151, /* 7602176 */
3176 7733233, /* 7733248 */
3177 7864301, /* 7864320 */
3178 7995391, /* 7995392 */
3179 8126453, /* 8126464 */
3180 8257531, /* 8257536 */
3181 8388593, /* 8388608 */
3182 8519647, /* 8519680 */
3183 8650727, /* 8650752 */
3184 8781797, /* 8781824 */
3185 8912887, /* 8912896 */
3186 9043967, /* 9043968 */
3187 9175037, /* 9175040 */
3188 9306097, /* 9306112 */
3189 9437179, /* 9437184 */
3190 9568219, /* 9568256 */
3191 9699323, /* 9699328 */
3192 9830393, /* 9830400 */
3193 9961463, /* 9961472 */
3194 10092539, /* 10092544 */
3195 10223593, /* 10223616 */
3196 10354667, /* 10354688 */
3197 10485751, /* 10485760 */
3198 10616831, /* 10616832 */
3199 10747903, /* 10747904 */
3200 10878961, /* 10878976 */
3201 11010037, /* 11010048 */
3202 11141113, /* 11141120 */
3203 11272181, /* 11272192 */
3204 11403247, /* 11403264 */
3205 11534329, /* 11534336 */
3206 11665403, /* 11665408 */
3207 11796469, /* 11796480 */
3208 11927551, /* 11927552 */
3209 12058621, /* 12058624 */
3210 12189677, /* 12189696 */
3211 12320753, /* 12320768 */
3212 12451807, /* 12451840 */
3213 12582893, /* 12582912 */
3214 12713959, /* 12713984 */
3215 12845033, /* 12845056 */
3216 12976121, /* 12976128 */
3217 13107197, /* 13107200 */
3218 13238263, /* 13238272 */
3219 13369333, /* 13369344 */
3220 13500373, /* 13500416 */
3221 13631477, /* 13631488 */
3222 13762549, /* 13762560 */
3223 13893613, /* 13893632 */
3224 14024671, /* 14024704 */
3225 14155763, /* 14155776 */
3226 14286809, /* 14286848 */
3227 14417881, /* 14417920 */
3228 14548979, /* 14548992 */
3229 14680063, /* 14680064 */
3230 14811133, /* 14811136 */
3231 14942197, /* 14942208 */
3232 15073277, /* 15073280 */
3233 15204349, /* 15204352 */
3234 15335407, /* 15335424 */
3235 15466463, /* 15466496 */
3236 15597559, /* 15597568 */
3237 15728611, /* 15728640 */
3238 15859687, /* 15859712 */
3239 15990781, /* 15990784 */
3240 16121849, /* 16121856 */
3241 16252919, /* 16252928 */
3242 16383977, /* 16384000 */
3243 16515067, /* 16515072 */
3244 16646099, /* 16646144 */
3245 16777213, /* 16777216 */
3246 16908263, /* 16908288 */
3247 17039339, /* 17039360 */
3248 17170429, /* 17170432 */
3249 17301463, /* 17301504 */
3250 17432561, /* 17432576 */
3251 17563633, /* 17563648 */
3252 17694709, /* 17694720 */
3253 17825791, /* 17825792 */
3254 17956849, /* 17956864 */
3255 18087899, /* 18087936 */
3256 18219001, /* 18219008 */
3257 18350063, /* 18350080 */
3258 18481097, /* 18481152 */
3259 18612211, /* 18612224 */
3260 18743281, /* 18743296 */
3261 18874367, /* 18874368 */
3262 19005433, /* 19005440 */
3263 19136503, /* 19136512 */
3264 19267561, /* 19267584 */
3265 19398647, /* 19398656 */
3266 19529717, /* 19529728 */
3267 19660799, /* 19660800 */
3268 19791869, /* 19791872 */
3269 19922923, /* 19922944 */
3270 20054011, /* 20054016 */
3271 20185051, /* 20185088 */
3272 20316151, /* 20316160 */
3273 20447191, /* 20447232 */
3274 20578297, /* 20578304 */
3275 20709347, /* 20709376 */
3276 20840429, /* 20840448 */
3277 20971507, /* 20971520 */
3278 21102583, /* 21102592 */
3279 21233651, /* 21233664 */
3280 21364727, /* 21364736 */
3281 21495797, /* 21495808 */
3282 21626819, /* 21626880 */
3283 21757951, /* 21757952 */
3284 21889019, /* 21889024 */
3285 22020091, /* 22020096 */
3286 22151167, /* 22151168 */
3287 22282199, /* 22282240 */
3288 22413289, /* 22413312 */
3289 22544351, /* 22544384 */
3290 22675403, /* 22675456 */
3291 22806521, /* 22806528 */
3292 22937591, /* 22937600 */
3293 23068667, /* 23068672 */
3294 23199731, /* 23199744 */
3295 23330773, /* 23330816 */
3296 23461877, /* 23461888 */
3297 23592937, /* 23592960 */
3298 23724031, /* 23724032 */
3299 23855101, /* 23855104 */
3300 23986159, /* 23986176 */
3301 24117217, /* 24117248 */
3302 24248299, /* 24248320 */
3303 24379391, /* 24379392 */
3304 24510463, /* 24510464 */
3305 24641479, /* 24641536 */
3306 24772603, /* 24772608 */
3307 24903667, /* 24903680 */
3308 25034731, /* 25034752 */
3309 25165813, /* 25165824 */
3310 25296893, /* 25296896 */
3311 25427957, /* 25427968 */
3312 25559033, /* 25559040 */
3313 25690097, /* 25690112 */
3314 25821179, /* 25821184 */
3315 25952243, /* 25952256 */
3316 26083273, /* 26083328 */
3317 26214379, /* 26214400 */
3318 26345471, /* 26345472 */
3319 26476543, /* 26476544 */
3320 26607611, /* 26607616 */
3321 26738687, /* 26738688 */
3322 26869753, /* 26869760 */
3323 27000817, /* 27000832 */
3324 27131903, /* 27131904 */
3325 27262931, /* 27262976 */
3326 27394019, /* 27394048 */
3327 27525109, /* 27525120 */
3328 27656149, /* 27656192 */
3329 27787213, /* 27787264 */
3330 27918323, /* 27918336 */
3331 28049407, /* 28049408 */
3332 28180459, /* 28180480 */
3333 28311541, /* 28311552 */
3334 28442551, /* 28442624 */
3335 28573673, /* 28573696 */
3336 28704749, /* 28704768 */
3337 28835819, /* 28835840 */
3338 28966909, /* 28966912 */
3339 29097977, /* 29097984 */
3340 29229047, /* 29229056 */
3341 29360087, /* 29360128 */
3342 29491193, /* 29491200 */
3343 29622269, /* 29622272 */
3344 29753341, /* 29753344 */
3345 29884411, /* 29884416 */
3346 30015481, /* 30015488 */
3347 30146531, /* 30146560 */
3348 30277627, /* 30277632 */
3349 30408701, /* 30408704 */
3350 30539749, /* 30539776 */
3351 30670847, /* 30670848 */
3352 30801917, /* 30801920 */
3353 30932987, /* 30932992 */
3354 31064063, /* 31064064 */
3355 31195117, /* 31195136 */
3356 31326181, /* 31326208 */
3357 31457269, /* 31457280 */
3358 31588351, /* 31588352 */
3359 31719409, /* 31719424 */
3360 31850491, /* 31850496 */
3361 31981567, /* 31981568 */
3362 32112607, /* 32112640 */
3363 32243707, /* 32243712 */
3364 32374781, /* 32374784 */
3365 32505829, /* 32505856 */
3366 32636921, /* 32636928 */
3367 32767997, /* 32768000 */
3368 32899037, /* 32899072 */
3369 33030121, /* 33030144 */
3370 33161201, /* 33161216 */
3371 33292283, /* 33292288 */
3372 33423319, /* 33423360 */
3373 33554393, /* 33554432 */
3374 33685493, /* 33685504 */
3375 33816571, /* 33816576 */
3376 33947621, /* 33947648 */
3377 34078699, /* 34078720 */
3378 34209787, /* 34209792 */
3379 34340861, /* 34340864 */
3380 34471933, /* 34471936 */
3381 34602991, /* 34603008 */
3382 34734079, /* 34734080 */
3383 34865141, /* 34865152 */
3384 34996223, /* 34996224 */
3385 35127263, /* 35127296 */
3386 35258347, /* 35258368 */
3387 35389423, /* 35389440 */
3388 35520467, /* 35520512 */
3389 35651579, /* 35651584 */
3390 35782613, /* 35782656 */
3391 35913727, /* 35913728 */
3392 36044797, /* 36044800 */
3393 36175871, /* 36175872 */
3394 36306937, /* 36306944 */
3395 36438013, /* 36438016 */
3396 36569083, /* 36569088 */
3397 36700159, /* 36700160 */
3398 36831227, /* 36831232 */
3399 36962291, /* 36962304 */
3400 37093373, /* 37093376 */
3401 37224437, /* 37224448 */
3402 37355503, /* 37355520 */
3403 37486591, /* 37486592 */
3404 37617653, /* 37617664 */
3405 37748717, /* 37748736 */
3406 37879783, /* 37879808 */
3407 38010871, /* 38010880 */
3408 38141951, /* 38141952 */
3409 38273023, /* 38273024 */
3410 38404081, /* 38404096 */
3411 38535151, /* 38535168 */
3412 38666219, /* 38666240 */
3413 38797303, /* 38797312 */
3414 38928371, /* 38928384 */
3415 39059431, /* 39059456 */
3416 39190519, /* 39190528 */
3417 39321599, /* 39321600 */
3418 39452671, /* 39452672 */
3419 39583727, /* 39583744 */
3420 39714799, /* 39714816 */
3421 39845887, /* 39845888 */
3422 39976939, /* 39976960 */
3423 40108027, /* 40108032 */
3424 40239103, /* 40239104 */
3425 40370173, /* 40370176 */
3426 40501231, /* 40501248 */
3427 40632313, /* 40632320 */
3428 40763369, /* 40763392 */
3429 40894457, /* 40894464 */
3430 41025499, /* 41025536 */
3431 41156569, /* 41156608 */
3432 41287651, /* 41287680 */
3433 41418739, /* 41418752 */
3434 41549803, /* 41549824 */
3435 41680871, /* 41680896 */
3436 41811949, /* 41811968 */
3437 41943023, /* 41943040 */
3438 42074101, /* 42074112 */
3439 42205183, /* 42205184 */
3440 42336253, /* 42336256 */
3441 42467317, /* 42467328 */
3442 42598397, /* 42598400 */
3443 42729437, /* 42729472 */
3444 42860537, /* 42860544 */
3445 42991609, /* 42991616 */
3446 43122683, /* 43122688 */
3447 43253759, /* 43253760 */
3448 43384813, /* 43384832 */
3449 43515881, /* 43515904 */
3450 43646963, /* 43646976 */
3451 43778011, /* 43778048 */
3452 43909111, /* 43909120 */
3453 44040187, /* 44040192 */
3454 44171261, /* 44171264 */
3455 44302303, /* 44302336 */
3456 44433391, /* 44433408 */
3457 44564461, /* 44564480 */
3458 44695549, /* 44695552 */
3459 44826611, /* 44826624 */
3460 44957687, /* 44957696 */
3461 45088739, /* 45088768 */
3462 45219827, /* 45219840 */
3463 45350869, /* 45350912 */
3464 45481973, /* 45481984 */
3465 45613039, /* 45613056 */
3466 45744121, /* 45744128 */
3467 45875191, /* 45875200 */
3468 46006249, /* 46006272 */
3469 46137319, /* 46137344 */
3470 46268381, /* 46268416 */
3471 46399471, /* 46399488 */
3472 46530557, /* 46530560 */
3473 46661627, /* 46661632 */
3474 46792699, /* 46792704 */
3475 46923761, /* 46923776 */
3476 47054809, /* 47054848 */
3477 47185907, /* 47185920 */
3478 47316991, /* 47316992 */
3479 47448061, /* 47448064 */
3480 47579131, /* 47579136 */
3481 47710207, /* 47710208 */
3482 47841257, /* 47841280 */
3483 47972341, /* 47972352 */
3484 48103417, /* 48103424 */
3485 48234451, /* 48234496 */
3486 48365563, /* 48365568 */
3487 48496639, /* 48496640 */
3488 48627697, /* 48627712 */
3489 48758783, /* 48758784 */
3490 48889837, /* 48889856 */
3491 49020913, /* 49020928 */
3492 49151987, /* 49152000 */
3493 49283063, /* 49283072 */
3494 49414111, /* 49414144 */
3495 49545193, /* 49545216 */
3496 49676267, /* 49676288 */
3497 49807327, /* 49807360 */
3498 49938431, /* 49938432 */
3499 50069497, /* 50069504 */
3500 50200573, /* 50200576 */
3501 50331599, /* 50331648 */
3502 50462683, /* 50462720 */
3503 50593783, /* 50593792 */
3504 50724859, /* 50724864 */
3505 50855899, /* 50855936 */
3506 50987003, /* 50987008 */
3507 51118069, /* 51118080 */
3508 51249131, /* 51249152 */
3509 51380179, /* 51380224 */
3510 51511277, /* 51511296 */
3511 51642341, /* 51642368 */
3512 51773431, /* 51773440 */
3513 51904511, /* 51904512 */
3514 52035569, /* 52035584 */
3515 52166641, /* 52166656 */
3516 52297717, /* 52297728 */
3517 52428767, /* 52428800 */
3518 52559867, /* 52559872 */
3519 52690919, /* 52690944 */
3520 52821983, /* 52822016 */
3521 52953077, /* 52953088 */
3522 53084147, /* 53084160 */
3523 53215229, /* 53215232 */
3524 53346301, /* 53346304 */
3525 53477357, /* 53477376 */
3526 53608441, /* 53608448 */
3527 53739493, /* 53739520 */
3528 53870573, /* 53870592 */
3529 54001663, /* 54001664 */
3530 54132721, /* 54132736 */
3531 54263789, /* 54263808 */
3532 54394877, /* 54394880 */
3533 54525917, /* 54525952 */
3534 54656983, /* 54657024 */
3535 54788089, /* 54788096 */
3536 54919159, /* 54919168 */
3537 55050217, /* 55050240 */
3538 55181311, /* 55181312 */
3539 55312351, /* 55312384 */
3540 55443433, /* 55443456 */
3541 55574507, /* 55574528 */
3542 55705589, /* 55705600 */
3543 55836659, /* 55836672 */
3544 55967701, /* 55967744 */
3545 56098813, /* 56098816 */
3546 56229881, /* 56229888 */
3547 56360911, /* 56360960 */
3548 56491993, /* 56492032 */
3549 56623093, /* 56623104 */
3550 56754167, /* 56754176 */
3551 56885219, /* 56885248 */
3552 57016319, /* 57016320 */
3553 57147379, /* 57147392 */
3554 57278461, /* 57278464 */
3555 57409529, /* 57409536 */
3556 57540599, /* 57540608 */
3557 57671671, /* 57671680 */
3558 57802739, /* 57802752 */
3559 57933817, /* 57933824 */
3560 58064861, /* 58064896 */
3561 58195939, /* 58195968 */
3562 58327039, /* 58327040 */
3563 58458091, /* 58458112 */
3564 58589161, /* 58589184 */
3565 58720253, /* 58720256 */
3566 58851307, /* 58851328 */
3567 58982389, /* 58982400 */
3568 59113469, /* 59113472 */
3569 59244539, /* 59244544 */
3570 59375587, /* 59375616 */
3571 59506679, /* 59506688 */
3572 59637733, /* 59637760 */
3573 59768831, /* 59768832 */
3574 59899901, /* 59899904 */
3575 60030953, /* 60030976 */
3576 60162029, /* 60162048 */
3577 60293119, /* 60293120 */
3578 60424183, /* 60424192 */
3579 60555227, /* 60555264 */
3580 60686321, /* 60686336 */
3581 60817397, /* 60817408 */
3582 60948479, /* 60948480 */
3583 61079531, /* 61079552 */
3584 61210603, /* 61210624 */
3585 61341659, /* 61341696 */
3586 61472753, /* 61472768 */
3587 61603811, /* 61603840 */
3588 61734899, /* 61734912 */
3589 61865971, /* 61865984 */
3590 61997053, /* 61997056 */
3591 62128127, /* 62128128 */
3592 62259193, /* 62259200 */
3593 62390261, /* 62390272 */
3594 62521331, /* 62521344 */
3595 62652407, /* 62652416 */
3596 62783477, /* 62783488 */
3597 62914549, /* 62914560 */
3598 63045613, /* 63045632 */
3599 63176693, /* 63176704 */
3600 63307763, /* 63307776 */
3601 63438839, /* 63438848 */
3602 63569917, /* 63569920 */
3603 63700991, /* 63700992 */
3604 63832057, /* 63832064 */
3605 63963131, /* 63963136 */
3606 64094207, /* 64094208 */
3607 64225267, /* 64225280 */
3608 64356349, /* 64356352 */
3609 64487417, /* 64487424 */
3610 64618493, /* 64618496 */
3611 64749563, /* 64749568 */
3612 64880587, /* 64880640 */
3613 65011703, /* 65011712 */
3614 65142769, /* 65142784 */
3615 65273851, /* 65273856 */
3616 65404909, /* 65404928 */
3617 65535989, /* 65536000 */
3618 65667067, /* 65667072 */
3619 65798137, /* 65798144 */
3620 65929211, /* 65929216 */
3621 66060277, /* 66060288 */
3622 66191351, /* 66191360 */
3623 66322427, /* 66322432 */
3624 66453479, /* 66453504 */
3625 66584561, /* 66584576 */
3626 66715643, /* 66715648 */
3627 66846709, /* 66846720 */
3628 66977767, /* 66977792 */
3629 67108859, /* 67108864 */
3630 67239883, /* 67239936 */
3631 67370999, /* 67371008 */
3632 67502063, /* 67502080 */
3633 67633127, /* 67633152 */
3634 67764223, /* 67764224 */
3635 67895251, /* 67895296 */
3636 68026363, /* 68026368 */
3637 68157433, /* 68157440 */
3638 68288503, /* 68288512 */
3639 68419567, /* 68419584 */
3640 68550631, /* 68550656 */
3641 68681719, /* 68681728 */
3642 68812769, /* 68812800 */
3643 68943851, /* 68943872 */
3644 69074933, /* 69074944 */
3645 69205987, /* 69206016 */
3646 69337087, /* 69337088 */
3647 69468151, /* 69468160 */
3648 69599221, /* 69599232 */
3649 69730303, /* 69730304 */
3650 69861331, /* 69861376 */
3651 69992443, /* 69992448 */
3652 70123513, /* 70123520 */
3653 70254563, /* 70254592 */
3654 70385641, /* 70385664 */
3655 70516729, /* 70516736 */
3656 70647793, /* 70647808 */
3657 70778861, /* 70778880 */
3658 70909933, /* 70909952 */
3659 71041021, /* 71041024 */
3660 71172091, /* 71172096 */
3661 71303153, /* 71303168 */
3662 71434229, /* 71434240 */
3663 71565283, /* 71565312 */
3664 71696363, /* 71696384 */
3665 71827423, /* 71827456 */
3666 71958521, /* 71958528 */
3667 72089573, /* 72089600 */
3668 72220663, /* 72220672 */
3669 72351733, /* 72351744 */
3670 72482807, /* 72482816 */
3671 72613861, /* 72613888 */
3672 72744937, /* 72744960 */
3673 72876031, /* 72876032 */
3674 73007089, /* 73007104 */
3675 73138171, /* 73138176 */
3676 73269247, /* 73269248 */
3677 73400311, /* 73400320 */
3678 73531379, /* 73531392 */
3679 73662461, /* 73662464 */
3680 73793521, /* 73793536 */
3681 73924583, /* 73924608 */
3682 74055637, /* 74055680 */
3683 74186747, /* 74186752 */
3684 74317801, /* 74317824 */
3685 74448877, /* 74448896 */
3686 74579951, /* 74579968 */
3687 74711027, /* 74711040 */
3688 74842099, /* 74842112 */
3689 74973181, /* 74973184 */
3690 75104243, /* 75104256 */
3691 75235327, /* 75235328 */
3692 75366397, /* 75366400 */
3693 75497467, /* 75497472 */
3694 75628513, /* 75628544 */
3695 75759613, /* 75759616 */
3696 75890653, /* 75890688 */
3697 76021661, /* 76021760 */
3698 76152821, /* 76152832 */
3699 76283897, /* 76283904 */
3700 76414973, /* 76414976 */
3701 76546039, /* 76546048 */
3702 76677113, /* 76677120 */
3703 76808119, /* 76808192 */
3704 76939253, /* 76939264 */
3705 77070317, /* 77070336 */
3706 77201347, /* 77201408 */
3707 77332471, /* 77332480 */
3708 77463541, /* 77463552 */
3709 77594599, /* 77594624 */
3710 77725691, /* 77725696 */
3711 77856767, /* 77856768 */
3712 77987821, /* 77987840 */
3713 78118903, /* 78118912 */
3714 78249973, /* 78249984 */
3715 78381047, /* 78381056 */
3716 78512101, /* 78512128 */
3717 78643199, /* 78643200 */
3718 78774259, /* 78774272 */
3719 78905303, /* 78905344 */
3720 79036411, /* 79036416 */
3721 79167479, /* 79167488 */
3722 79298543, /* 79298560 */
3723 79429619, /* 79429632 */
3724 79560673, /* 79560704 */
3725 79691761, /* 79691776 */
3726 79822829, /* 79822848 */
3727 79953901, /* 79953920 */
3728 80084969, /* 80084992 */
3729 80216063, /* 80216064 */
3730 80347103, /* 80347136 */
3731 80478199, /* 80478208 */
3732 80609279, /* 80609280 */
3733 80740339, /* 80740352 */
3734 80871419, /* 80871424 */
3735 81002489, /* 81002496 */
3736 81133567, /* 81133568 */
3737 81264587, /* 81264640 */
3738 81395683, /* 81395712 */
3739 81526763, /* 81526784 */
3740 81657841, /* 81657856 */
3741 81788923, /* 81788928 */
3742 81919993, /* 81920000 */
3743 82051043, /* 82051072 */
3744 82182137, /* 82182144 */
3745 82313213, /* 82313216 */
3746 82444279, /* 82444288 */
3747 82575331, /* 82575360 */
3748 82706431, /* 82706432 */
3749 82837501, /* 82837504 */
3750 82968563, /* 82968576 */
3751 83099641, /* 83099648 */
3752 83230717, /* 83230720 */
3753 83361781, /* 83361792 */
3754 83492863, /* 83492864 */
3755 83623931, /* 83623936 */
3756 83754997, /* 83755008 */
3757 83886053, /* 83886080 */
3758 84017117, /* 84017152 */
3759 84148213, /* 84148224 */
3760 84279277, /* 84279296 */
3761 84410353, /* 84410368 */
3762 84541421, /* 84541440 */
3763 84672487, /* 84672512 */
3764 84803581, /* 84803584 */
3765 84934621, /* 84934656 */
3766 85065719, /* 85065728 */
3767 85196789, /* 85196800 */
3768 85327849, /* 85327872 */
3769 85458929, /* 85458944 */
3770 85589989, /* 85590016 */
3771 85721081, /* 85721088 */
3772 85852147, /* 85852160 */
3773 85983217, /* 85983232 */
3774 86114279, /* 86114304 */
3775 86245343, /* 86245376 */
3776 86376443, /* 86376448 */
3777 86507507, /* 86507520 */
3778 86638577, /* 86638592 */
3779 86769647, /* 86769664 */
3780 86900731, /* 86900736 */
3781 87031759, /* 87031808 */
3782 87162857, /* 87162880 */
3783 87293939, /* 87293952 */
3784 87425021, /* 87425024 */
3785 87556087, /* 87556096 */
3786 87687167, /* 87687168 */
3787 87818239, /* 87818240 */
3788 87949307, /* 87949312 */
3789 88080359, /* 88080384 */
3790 88211449, /* 88211456 */
3791 88342519, /* 88342528 */
3792 88473569, /* 88473600 */
3793 88604653, /* 88604672 */
3794 88735721, /* 88735744 */
3795 88866797, /* 88866816 */
3796 88997827, /* 88997888 */
3797 89128939, /* 89128960 */
3798 89260027, /* 89260032 */
3799 89391103, /* 89391104 */
3800 89522171, /* 89522176 */
3801 89653217, /* 89653248 */
3802 89784313, /* 89784320 */
3803 89915383, /* 89915392 */
3804 90046441, /* 90046464 */
3805 90177533, /* 90177536 */
3806 90308599, /* 90308608 */
3807 90439667, /* 90439680 */
3808 90570751, /* 90570752 */
3809 90701797, /* 90701824 */
3810 90832871, /* 90832896 */
3811 90963967, /* 90963968 */
3812 91095013, /* 91095040 */
3813 91226101, /* 91226112 */
3814 91357177, /* 91357184 */
3815 91488251, /* 91488256 */
3816 91619321, /* 91619328 */
3817 91750391, /* 91750400 */
3818 91881443, /* 91881472 */
3819 92012537, /* 92012544 */
3820 92143609, /* 92143616 */
3821 92274671, /* 92274688 */
3822 92405723, /* 92405760 */
3823 92536823, /* 92536832 */
3824 92667863, /* 92667904 */
3825 92798969, /* 92798976 */
3826 92930039, /* 92930048 */
3827 93061117, /* 93061120 */
3828 93192191, /* 93192192 */
3829 93323249, /* 93323264 */
3830 93454307, /* 93454336 */
3831 93585379, /* 93585408 */
3832 93716471, /* 93716480 */
3833 93847549, /* 93847552 */
3834 93978559, /* 93978624 */
3835 94109681, /* 94109696 */
3836 94240733, /* 94240768 */
3837 94371833, /* 94371840 */
3838 94502899, /* 94502912 */
3839 94633963, /* 94633984 */
3840 94765039, /* 94765056 */
3841 94896119, /* 94896128 */
3842 95027197, /* 95027200 */
3843 95158249, /* 95158272 */
3844 95289329, /* 95289344 */
3845 95420401, /* 95420416 */
3846 95551487, /* 95551488 */
3847 95682541, /* 95682560 */
3848 95813621, /* 95813632 */
3849 95944691, /* 95944704 */
3850 96075739, /* 96075776 */
3851 96206839, /* 96206848 */
3852 96337919, /* 96337920 */
3853 96468979, /* 96468992 */
3854 96600041, /* 96600064 */
3855 96731101, /* 96731136 */
3856 96862169, /* 96862208 */
3857 96993269, /* 96993280 */
3858 97124347, /* 97124352 */
3859 97255409, /* 97255424 */
3860 97386467, /* 97386496 */
3861 97517543, /* 97517568 */
3862 97648637, /* 97648640 */
3863 97779701, /* 97779712 */
3864 97910759, /* 97910784 */
3865 98041831, /* 98041856 */
3866 98172887, /* 98172928 */
3867 98303999, /* 98304000 */
3868 98435063, /* 98435072 */
3869 98566121, /* 98566144 */
3870 98697187, /* 98697216 */
3871 98828281, /* 98828288 */
3872 98959337, /* 98959360 */
3873 99090427, /* 99090432 */
3874 99221489, /* 99221504 */
3875 99352567, /* 99352576 */
3876 99483647, /* 99483648 */
3877 99614689, /* 99614720 */
3878 99745787, /* 99745792 */
3879 99876851, /* 99876864 */
3880 100007927, /* 100007936 */
3881 100138979, /* 100139008 */
3882 100270069, /* 100270080 */
3883 100401139, /* 100401152 */
3884 100532207, /* 100532224 */
3885 100663291, /* 100663296 */
3886 100794319, /* 100794368 */
3887 100925431, /* 100925440 */
3888 101056507, /* 101056512 */
3889 101187577, /* 101187584 */
3890 101318647, /* 101318656 */
3891 101449717, /* 101449728 */
3892 101580793, /* 101580800 */
3893 101711839, /* 101711872 */
3894 101842931, /* 101842944 */
3895 101974009, /* 101974016 */
3896 102105049, /* 102105088 */
3897 102236149, /* 102236160 */
3898 102367189, /* 102367232 */
3899 102498301, /* 102498304 */
3900 102629369, /* 102629376 */
3901 102760387, /* 102760448 */
3902 102891499, /* 102891520 */
3903 103022537, /* 103022592 */
3904 103153649, /* 103153664 */
3905 103284733, /* 103284736 */
3906 103415791, /* 103415808 */
3907 103546879, /* 103546880 */
3908 103677949, /* 103677952 */
3909 103809011, /* 103809024 */
3910 103940093, /* 103940096 */
3911 104071157, /* 104071168 */
3912 104202233, /* 104202240 */
3913 104333311, /* 104333312 */
3914 104464369, /* 104464384 */
3915 104595397, /* 104595456 */
3916 104726527, /* 104726528 */
3917 104857589, /* 104857600 */
3918 104988641, /* 104988672 */
3919 105119741, /* 105119744 */
3920 105250811, /* 105250816 */
3921 105381841, /* 105381888 */
3922 105512951, /* 105512960 */
3923 105644029, /* 105644032 */
3924 105775079, /* 105775104 */
3925 105906167, /* 105906176 */
3926 106037237, /* 106037248 */
3927 106168319, /* 106168320 */
3928 106299379, /* 106299392 */
3929 106430449, /* 106430464 */
3930 106561523, /* 106561536 */
3931 106692601, /* 106692608 */
3932 106823677, /* 106823680 */
3933 106954747, /* 106954752 */
3934 107085799, /* 107085824 */
3935 107216891, /* 107216896 */
3936 107347943, /* 107347968 */
3937 107479033, /* 107479040 */
3938 107610079, /* 107610112 */
3939 107741167, /* 107741184 */
3940 107872249, /* 107872256 */
3941 108003323, /* 108003328 */
3942 108134393, /* 108134400 */
3943 108265459, /* 108265472 */
3944 108396521, /* 108396544 */
3945 108527603, /* 108527616 */
3946 108658681, /* 108658688 */
3947 108789727, /* 108789760 */
3948 108920831, /* 108920832 */
3949 109051903, /* 109051904 */
3950 109182947, /* 109182976 */
3951 109314043, /* 109314048 */
3952 109445107, /* 109445120 */
3953 109576189, /* 109576192 */
3954 109707253, /* 109707264 */
3955 109838293, /* 109838336 */
3956 109969403, /* 109969408 */
3957 110100409, /* 110100480 */
3958 110231531, /* 110231552 */
3959 110362559, /* 110362624 */
3960 110493661, /* 110493696 */
3961 110624753, /* 110624768 */
3962 110755793, /* 110755840 */
3963 110886883, /* 110886912 */
3964 111017983, /* 111017984 */
3965 111148963, /* 111149056 */
3966 111280121, /* 111280128 */
3967 111411173, /* 111411200 */
3968 111542261, /* 111542272 */
3969 111673343, /* 111673344 */
3970 111804389, /* 111804416 */
3971 111935459, /* 111935488 */
3972 112066553, /* 112066560 */
3973 112197629, /* 112197632 */
3974 112328683, /* 112328704 */
3975 112459751, /* 112459776 */
3976 112590839, /* 112590848 */
3977 112721893, /* 112721920 */
3978 112852981, /* 112852992 */
3979 112984061, /* 112984064 */
3980 113115133, /* 113115136 */
3981 113246183, /* 113246208 */
3982 113377279, /* 113377280 */
3983 113508319, /* 113508352 */
3984 113639419, /* 113639424 */
3985 113770457, /* 113770496 */
3986 113901553, /* 113901568 */
3987 114032599, /* 114032640 */
3988 114163703, /* 114163712 */
3989 114294721, /* 114294784 */
3990 114425807, /* 114425856 */
3991 114556913, /* 114556928 */
3992 114687977, /* 114688000 */
3993 114819031, /* 114819072 */
3994 114950131, /* 114950144 */
3995 115081189, /* 115081216 */
3996 115212287, /* 115212288 */
3997 115343341, /* 115343360 */
3998 115474417, /* 115474432 */
3999 115605467, /* 115605504 */
4000 115736539, /* 115736576 */
4001 115867627, /* 115867648 */
4002 115998719, /* 115998720 */
4003 116129789, /* 116129792 */
4004 116260849, /* 116260864 */
4005 116391917, /* 116391936 */
4006 116523007, /* 116523008 */
4007 116654077, /* 116654080 */
4008 116785133, /* 116785152 */
4009 116916223, /* 116916224 */
4010 117047291, /* 117047296 */
4011 117178367, /* 117178368 */
4012 117309421, /* 117309440 */
4013 117440509, /* 117440512 */
4014 117571523, /* 117571584 */
4015 117702649, /* 117702656 */
4016 117833711, /* 117833728 */
4017 117964793, /* 117964800 */
4018 118095853, /* 118095872 */
4019 118226893, /* 118226944 */
4020 118358003, /* 118358016 */
4021 118489081, /* 118489088 */
4022 118620143, /* 118620160 */
4023 118751207, /* 118751232 */
4024 118882279, /* 118882304 */
4025 119013347, /* 119013376 */
4026 119144447, /* 119144448 */
4027 119275511, /* 119275520 */
4028 119406587, /* 119406592 */
4029 119537653, /* 119537664 */
4030 119668723, /* 119668736 */
4031 119799803, /* 119799808 */
4032 119930873, /* 119930880 */
4033 120061951, /* 120061952 */
4034 120193019, /* 120193024 */
4035 120324077, /* 120324096 */
4036 120455147, /* 120455168 */
4037 120586231, /* 120586240 */
4038 120717307, /* 120717312 */
4039 120848353, /* 120848384 */
4040 120979447, /* 120979456 */
4041 121110523, /* 121110528 */
4042 121241597, /* 121241600 */
4043 121372649, /* 121372672 */
4044 121503737, /* 121503744 */
4045 121634801, /* 121634816 */
4046 121765871, /* 121765888 */
4047 121896949, /* 121896960 */
4048 122028019, /* 122028032 */
4049 122159101, /* 122159104 */
4050 122290171, /* 122290176 */
4051 122421241, /* 122421248 */
4052 122552317, /* 122552320 */
4053 122683391, /* 122683392 */
4054 122814463, /* 122814464 */
4055 122945527, /* 122945536 */
4056 123076601, /* 123076608 */
4057 123207677, /* 123207680 */
4058 123338737, /* 123338752 */
4059 123469783, /* 123469824 */
4060 123600857, /* 123600896 */
4061 123731963, /* 123731968 */
4062 123863023, /* 123863040 */
4063 123994099, /* 123994112 */
4064 124125161, /* 124125184 */
4065 124256243, /* 124256256 */
4066 124387321, /* 124387328 */
4067 124518397, /* 124518400 */
4068 124649449, /* 124649472 */
4069 124780531, /* 124780544 */
4070 124911601, /* 124911616 */
4071 125042663, /* 125042688 */
4072 125173759, /* 125173760 */
4073 125304787, /* 125304832 */
4074 125435897, /* 125435904 */
4075 125566963, /* 125566976 */
4076 125698021, /* 125698048 */
4077 125829103, /* 125829120 */
4078 125960189, /* 125960192 */
4079 126091241, /* 126091264 */
4080 126222293, /* 126222336 */
4081 126353407, /* 126353408 */
4082 126484469, /* 126484480 */
4083 126615551, /* 126615552 */
4084 126746623, /* 126746624 */
4085 126877693, /* 126877696 */
4086 127008733, /* 127008768 */
4087 127139833, /* 127139840 */
4088 127270849, /* 127270912 */
4089 127401947, /* 127401984 */
4090 127533047, /* 127533056 */
4091 127664113, /* 127664128 */
4092 127795181, /* 127795200 */
4093 127926263, /* 127926272 */
4094 128057327, /* 128057344 */
4095 128188409, /* 128188416 */
4096 128319469, /* 128319488 */
4097 128450533, /* 128450560 */
4098 128581631, /* 128581632 */
4099 128712691, /* 128712704 */
4100 128843761, /* 128843776 */
4101 128974841, /* 128974848 */
4102 129105901, /* 129105920 */
4103 129236959, /* 129236992 */
4104 129368051, /* 129368064 */
4105 129499129, /* 129499136 */
4106 129630199, /* 129630208 */
4107 129761273, /* 129761280 */
4108 129892333, /* 129892352 */
4109 130023407, /* 130023424 */
4110 130154483, /* 130154496 */
4111 130285567, /* 130285568 */
4112 130416631, /* 130416640 */
4113 130547621, /* 130547712 */
4114 130678781, /* 130678784 */
4115 130809853, /* 130809856 */
4116 130940911, /* 130940928 */
4117 131071987, /* 131072000 */
4118 131203069, /* 131203072 */
4119 131334131, /* 131334144 */
4120 131465177, /* 131465216 */
4121 131596279, /* 131596288 */
4122 131727359, /* 131727360 */
4123 131858413, /* 131858432 */
4124 131989477, /* 131989504 */
4125 132120557, /* 132120576 */
4126 132251621, /* 132251648 */
4127 132382717, /* 132382720 */
4128 132513781, /* 132513792 */
4129 132644851, /* 132644864 */
4130 132775931, /* 132775936 */
4131 132907007, /* 132907008 */
4132 133038053, /* 133038080 */
4133 133169137, /* 133169152 */
4134 133300207, /* 133300224 */
4135 133431293, /* 133431296 */
4136 133562329, /* 133562368 */
4137 133693433, /* 133693440 */
4138 133824503, /* 133824512 */
4139 133955581, /* 133955584 */
4140 134086639, /* 134086656 */
4143 int sf_nearest_prime( int n
)
4150 return prime_table0
[(n
>>3)& 1023];
4152 else if( n
< 64*1024 )
4154 return prime_table1
[(n
>>6)&1023];
4156 else if( n
< 1024*1024 )
4158 return prime_table2
[(n
>>10)&1023];
4160 else if( n
< 128*1024*1024 )
4162 return prime_table3
[(n
>>17)&1023];
4164 else if( n
< 1024*1024*1024 )
4166 return prime_table3
[(n
>>20)&1023];
4169 return 134086639; /* too big for table, just use a big prime */