pix.c

Calc Software Package for Number Calc

/*
 * pix - number of primes less than a small value
 *
 * Copyright (C) 1999  Landon Curt Noll
 *
 * Calc is open software; you can redistribute it and/or modify it under
 * the terms of the version 2.1 of the GNU Lesser General Public License
 * as published by the Free Software Foundation.
 *
 * Calc is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
 * Public License for more details.
 *
 * A copy of version 2.1 of the GNU Lesser General Public License is
 * distributed with calc under the filename COPYING-LGPL.  You should have
 * received a copy with calc; if not, write to Free Software Foundation, Inc.
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * @(#) $Revision: 29.2 $
 * @(#) $Id: pix.c,v 29.2 2000/06/07 14:02:13 chongo Exp $
 * @(#) $Source: /usr/local/src/cmd/calc/RCS/pix.c,v $
 *
 * Under source code control:	1994/07/01 19:44:21
 * File existed as early as:	1994
 *
 * chongo <was here> /\oo/\	http://www.isthe.com/chongo/
 * Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/
 */


#include "zmath.h"
#include "prime.h"
#include "have_const.h"


/*
 * pi10b - number of primes <= 2^18 in multiples of 2^10
 *
 * pi10b[x]  ==	 pi(x*1024)		for 0 <= x <= 256
 */
CONST unsigned short pi10b[(MAX_PI10B/1024)+1+1] = {
    0, 172, 309, 439, 564, 685, 801, 916, 1028, 1142, 1254, 1362, 1469, 1580,
    1681, 1794, 1900, 2002, 2110, 2205, 2312, 2413, 2517, 2618, 2725, 2818,
    2918, 3016, 3124, 3221, 3314, 3414, 3512, 3619, 3716, 3808, 3908, 4006,
    4098, 4197, 4288, 4391, 4495, 4583, 4678, 4767, 4858, 4956, 5051, 5152,
    5239, 5339, 5432, 5520, 5616, 5711, 5814, 5908, 6003, 6094, 6179, 6270,
    6363, 6453, 6542, 6636, 6734, 6820, 6906, 6999, 7095, 7190, 7281, 7371,
    7465, 7550, 7649, 7733, 7824, 7915, 8009, 8103, 8187, 8277, 8363, 8453,
    8548, 8630, 8727, 8812, 8899, 9000, 9087, 9180, 9271, 9357, 9439, 9533,
    9618, 9708, 9805, 9886, 9971, 10062, 10151, 10236, 10324, 10416, 10499,
    10585, 10674, 10761, 10846, 10930, 11021, 11110, 11196, 11282, 11371, 11462,
    11554, 11641, 11729, 11816, 11900, 11987, 12079, 12163, 12251, 12333, 12425,
    12507, 12589, 12680, 12777, 12861, 12941, 13032, 13125, 13212, 13289, 13372,
    13452, 13546, 13631, 13712, 13807, 13894, 13982, 14072, 14159, 14242, 14327,
    14407, 14497, 14577, 14662, 14750, 14835, 14915, 14999, 15086, 15167, 15247,
    15334, 15408, 15495, 15585, 15670, 15758, 15843, 15925, 16003, 16097, 16173,
    16264, 16357, 16433, 16519, 16601, 16690, 16775, 16869, 16954, 17032, 17119,
    17200, 17282, 17369, 17457, 17536, 17623, 17704, 17789, 17877, 17957, 18038,
    18118, 18205, 18285, 18367, 18450, 18535, 18624, 18710, 18798, 18889, 18974,
    19045, 19130, 19213, 19290, 19370, 19453, 19541, 19628, 19709, 19797, 19876,
    19960, 20043, 20126, 20206, 20288, 20379, 20476, 20552, 20632, 20709, 20787,
    20870, 20946, 21022, 21109, 21191, 21272, 21359, 21446, 21527, 21613, 21695,
    21776, 21859, 21950, 22031, 22106, 22196, 22276, 22358, 22435, 22525, 22599,
    22678, 22765, 22845, 22925, 23000
};

/*
 * pi18b - primes found in a given 2^18 interval
 *
 * i<x
 * sum pi18b[i]	 ==  pi(x*262144)	for 0 <= x <= 16384
 * i=0
 */
CONST unsigned short pi18b[(MAX_PI18B/262144)+1] = {
    23000, 20390, 19556, 19079, 18761, 18482, 18256, 18087, 17903, 17794, 17706,
    17535, 17520, 17309, 17359, 17210, 17138, 17092, 17082, 16936, 16918, 16793,
    16865, 16731, 16680, 16699, 16734, 16562, 16528, 16547, 16460, 16451, 16456,
    16397, 16318, 16352, 16319, 16221, 16200, 16290, 16260, 16152, 16159, 16114,
    16148, 16103, 16086, 16011, 16096, 15887, 16003, 15907, 16006, 15904, 15960,
    15839, 15879, 15799, 15811, 15893, 15834, 15757, 15777, 15770, 15834, 15671,
    15833, 15670, 15653, 15735, 15617, 15685, 15604, 15625, 15545, 15668, 15640,
    15455, 15640, 15484, 15526, 15626, 15491, 15566, 15400, 15445, 15501, 15528,
    15459, 15401, 15378, 15471, 15475, 15381, 15426, 15357, 15262, 15387, 15411,
    15333, 15368, 15354, 15339, 15301, 15285, 15339, 15325, 15286, 15246, 15211,
    15244, 15293, 15183, 15252, 15364, 15276, 15236, 15198, 15050, 15180, 15159,
    15198, 15149, 15201, 15167, 15141, 15161, 15129, 15154, 15019, 14997, 15113,
    14998, 15082, 15116, 15087, 15024, 15076, 15098, 15028, 14952, 15150, 14991,
    15081, 14947, 15116, 15041, 15030, 14997, 15104, 15005, 15012, 14908, 15043,
    14867, 15050, 14935, 14884, 14876, 14931, 14935, 14961, 14913, 14843, 14913,
    14939, 14839, 14911, 14898, 14840, 14962, 14907, 14938, 14924, 14850, 14831,
    14820, 14884, 14862, 14820, 14792, 14787, 14848, 14689, 14841, 14735, 14835,
    14820, 14872, 14825, 14770, 14810, 14807, 14803, 14703, 14774, 14771, 14797,
    14716, 14726, 14747, 14752, 14733, 14733, 14685, 14727, 14656, 14657, 14744,
    14685, 14718, 14658, 14777, 14701, 14744, 14614, 14739, 14722, 14749, 14626,
    14591, 14633, 14669, 14682, 14695, 14567, 14620, 14651, 14650, 14599, 14659,
    14696, 14673, 14476, 14569, 14624, 14655, 14608, 14506, 14676, 14551, 14627,
    14588, 14696, 14578, 14560, 14470, 14547, 14535, 14636, 14469, 14674, 14639,
    14550, 14538, 14573, 14570, 14563, 14560, 14541, 14524, 14494, 14468, 14514,
    14582, 14577, 14419, 14537, 14569, 14421, 14494, 14509, 14569, 14429, 14501,
    14619, 14427, 14490, 14505, 14448, 14479, 14493, 14359, 14474, 14392, 14504,
    14479, 14499, 14444, 14560, 14359, 14399, 14334, 14491, 14423, 14448, 14359,
    14472, 14358, 14368, 14424, 14428, 14426, 14377, 14414, 14292, 14509, 14358,
    14488, 14529, 14371, 14355, 14446, 14275, 14409, 14444, 14358, 14294, 14390,
    14386, 14364, 14299, 14350, 14296, 14325, 14423, 14312, 14389, 14305, 14374,
    14353, 14364, 14339, 14270, 14285, 14424, 14389, 14191, 14381, 14346, 14316,
    14231, 14226, 14378, 14326, 14309, 14377, 14288, 14295, 14350, 14238, 14277,
    14238, 14348, 14190, 14272, 14316, 14227, 14405, 14187, 14299, 14358, 14267,
    14300, 14267, 14283, 14225, 14250, 14307, 14246, 14198, 14326, 14280, 14235,
    14227, 14305, 14129, 14244, 14131, 14294, 14181, 14294, 14204, 14177, 14193,
    14254, 14263, 14192, 14269, 14230, 14327, 14216, 14158, 14183, 14233, 14169,
    14294, 14256, 14186, 14180, 14165, 14222, 14121, 14212, 14121, 14182, 14229,
    14098, 14264, 14227, 14223, 14073, 14229, 14322, 14157, 14129, 14180, 14230,
    14161, 14281, 13912, 14174, 14163, 14153, 14150, 14009, 14166, 14307, 14054,
    14131, 14160, 14178, 14126, 14009, 14078, 14152, 14025, 14129, 14194, 14042,
    14126, 14078, 14265, 14129, 14115, 14053, 14118, 14064, 14120, 14148, 14076,
    14116, 14110, 13968, 13993, 14123, 14052, 14239, 14049, 14013, 13972, 14225,
    14051, 14077, 14064, 14093, 13998, 14041, 14143, 14041, 14156, 14060, 14116,
    14091, 14102, 14044, 14034, 14084, 14019, 14119, 14088, 14063, 14082, 14012,
    14127, 13937, 14014, 14053, 14129, 13956, 14132, 14123, 14034, 14094, 14076,
    13862, 13982, 13972, 14089, 14140, 13974, 14023, 14046, 13942, 14027, 13999,
    14023, 14067, 13955, 13932, 13957, 14011, 14102, 13972, 14066, 14011, 13971,
    13899, 13962, 13949, 14154, 14004, 13970, 13954, 14128, 13847, 13929, 13945,
    13941, 14029, 13947, 14040, 13995, 14035, 13922, 13938, 13969, 13852, 13955,
    13985, 13957, 14069, 13999, 13984, 14004, 14006, 13992, 13978, 13972, 13981,
    14056, 13912, 13861, 13831, 13964, 14009, 13971, 13992, 13876, 13990, 13990,
    13912, 13981, 13860, 13985, 13884, 13970, 13926, 13874, 13913, 13902, 13955,
    13935, 13852, 13862, 13892, 13975, 13857, 13870, 13912, 13823, 13850, 14063,
    13906, 13858, 13926, 13981, 13839, 13916, 13961, 13843, 13923, 13829, 13993,
    13901, 13904, 13948, 13870, 13878, 13902, 13909, 13834, 13934, 13832, 13785,
    13823, 13984, 13850, 13805, 13965, 13940, 13811, 13952, 13959, 13854, 13714,
    13865, 13829, 13856, 13871, 13854, 13898, 13896, 13962, 13857, 13862, 13821,
    13900, 13796, 13841, 13755, 13793, 13855, 13836, 13937, 13885, 13802, 13916,
    13870, 13843, 13847, 13818, 13800, 13866, 13885, 13836, 13978, 13791, 13847,
    13864, 13786, 13774, 13956, 13865, 13760, 13870, 13786, 13852, 13819, 13803,
    13794, 13934, 13798, 13844, 13799, 13754, 13718, 13836, 13922, 13814, 13786,
    13827, 13805, 13765, 13869, 13889, 13737, 13823, 13877, 13889, 13610, 13838,
    13813, 13792, 13808, 13971, 13773, 13749, 13713, 13734, 13755, 13735, 13705,
    13818, 13718, 13727, 13766, 13667, 13728, 13836, 13871, 13750, 13813, 13838,
    13889, 13693, 13847, 13782, 13737, 13776, 13723, 13831, 13775, 13711, 13916,
    13623, 13837, 13711, 13734, 13684, 13767, 13823, 13730, 13708, 13841, 13742,
    13686, 13742, 13686, 13704, 13652, 13669, 13657, 13869, 13788, 13731, 13776,
    13635, 13908, 13744, 13737, 13776, 13690, 13885, 13668, 13710, 13657, 13825,
    13560, 13745, 13754, 13656, 13745, 13601, 13672, 13616, 13799, 13801, 13640,
    13680, 13799, 13653, 13763, 13851, 13626, 13718, 13680, 13735, 13629, 13783,
    13714, 13727, 13640, 13716, 13705, 13761, 13599, 13790, 13671, 13701, 13714,
    13750, 13660, 13712, 13693, 13643, 13715, 13684, 13737, 13665, 13698, 13751,
    13709, 13647, 13583, 13710, 13702, 13634, 13718, 13817, 13689, 13638, 13594,
    13664, 13679, 13683, 13765, 13632, 13661, 13643, 13652, 13597, 13778, 13655,
    13603, 13581, 13703, 13601, 13742, 13765, 13708, 13652, 13649, 13642, 13726,
    13617, 13559, 13630, 13684, 13671, 13551, 13718, 13683, 13578, 13667, 13661,
    13616, 13664, 13565, 13675, 13564, 13662, 13589, 13710, 13620, 13647, 13669,
    13731, 13610, 13636, 13676, 13718, 13756, 13543, 13601, 13763, 13604, 13539,
    13637, 13569, 13551, 13697, 13685, 13601, 13634, 13620, 13640, 13617, 13501,
    13525, 13711, 13606, 13670, 13667, 13517, 13572, 13647, 13690, 13567, 13745,
    13643, 13590, 13682, 13601, 13593, 13568, 13557, 13624, 13567, 13522, 13602,
    13516, 13566, 13568, 13604, 13746, 13610, 13669, 13586, 13521, 13697, 13520,
    13610, 13713, 13631, 13550, 13661, 13691, 13616, 13598, 13628, 13495, 13553,
    13634, 13579, 13598, 13656, 13647, 13640, 13543, 13522, 13557, 13567, 13571,
    13506, 13484, 13594, 13615, 13525, 13527, 13511, 13606, 13602, 13787, 13558,
    13650, 13528, 13581, 13453, 13540, 13645, 13546, 13541, 13564, 13502, 13563,
    13641, 13579, 13573, 13532, 13609, 13565, 13547, 13499, 13586, 13574, 13517,
    13636, 13591, 13578, 13359, 13629, 13521, 13540, 13542, 13508, 13639, 13460,
    13631, 13500, 13589, 13561, 13557, 13480, 13616, 13602, 13534, 13472, 13384,
    13518, 13640, 13541, 13591, 13515, 13553, 13465, 13604, 13492, 13548, 13597,
    13408, 13552, 13478, 13538, 13578, 13526, 13507, 13626, 13520, 13589, 13600,
    13546, 13514, 13521, 13411, 13420, 13471, 13502, 13516, 13458, 13550, 13562,
    13702, 13542, 13494, 13506, 13347, 13452, 13572, 13441, 13500, 13556, 13472,
    13505, 13582, 13519, 13527, 13522, 13380, 13454, 13456, 13535, 13469, 13439,