Problem with included function in C

Claus · 10-20-2003, 01:58 PM

I have a problem with this function when i compile a program that uses it.

#include<math.h>

/* isprime. Checks if a number is prime or not
*/

int
isprime(int n)
{
int i = 1;
if(!(n%2)) return 0;
while(((i+=2) <= sqrt(n))&&(n%i));
return (n%i);
}

When i compile the main program that includes 'isprime' i get the next error:

/tmp/ccGfMjOV.o(.text+0x14): In function `isprime':
: undefined reference to `sqrt'
collect2: ld returned 1 exit status

Why I have this problem in some machines, and in others dont???

I'm compiling with GCC, and not with G++!

Thank you.

Hko · 10-20-2003, 02:40 PM

You need to compile it with the "-lm" option in order to link in the math libs, e.g.:

Code:

gcc -Wall -pedantic -ansi -lm -o isprime isprime.c

jim mcnamara · 10-20-2003, 02:41 PM

Try
gcc filename.c -lm

to include the math library.

Hko · 10-20-2003, 02:51 PM

Your function does have math bug though. I get:

Code:

heiko@hko:~/dummy$ ./isprime 2
2 is NOT a prime number.
heiko@hko:~/dummy$ ./isprime 3
3 is NOT a prime number.
heiko@hko:~/dummy$ ./isprime 7907
7907 is a prime number.   /* which is correct   */

...using this code:

Code:

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

int isprime(int n)
{
     int i = 1;
     if(!(n%2)) return 0;
     while(((i+=2) <= sqrt(n))&&(n%i));
     return (n%i);
}

int main(int argc, char *argv[])
{
     if (argc == 2) {
	  if (isprime(atoi(argv[1]))) {
	       printf("%s is a prime number.\n", argv[1]);
	  } else {
	       printf("%s is NOT a prime number.\n", argv[1]);
	  }
     } else {
	  fprintf(stderr, "Use: %s <number>\n", argv[0]);
     }
     return 0;
}

Kurt M. Weber · 10-20-2003, 04:27 PM

Just include a special case that checks to see if the number given is 2, and if so automatically output that it is a prime without going through all the other stuff.

Claus · 10-20-2003, 04:36 PM

I have corrected that bug, matter of fact i get noticed of it while this page was loading

.

Here goes the correct function.

#include<math.h>

/* isprime. Checks if a number is prime or not
*/

int
isprime(int n)
{
if ((n>1)&&(n<4)) return 1;
int i = 1;
if(!(n%2)) return 0;
while(((i+=2) <= sqrt(n))&&(n%i));
return (n%i);
}

And yeah, you all were right. With -lm did work.

Thank You.

(Notice the efficence with big numbers!!!).

jim mcnamara · 10-20-2003, 05:22 PM

Table driven math functions are a LOT faster, in this case 20 times faster. Assuming you prime function is used a lot and the numbers are sometimes bigger than 2000 - 3000 I did a short test.

The"long code" refers to the table driven long version.
Short code is your version. This is a test on the same random number set, run two times:

kcsdev:/home/jmcnama> time ./test 1
choice:1
Processing using short code... Done

real 0m6.88s
user 0m6.79s <--------------------------
sys 0m0.01s
kcsdev:/home/jmcnama> time ./test 0
choice:0
Processing using long code... Done

real 0m0.39s
user 0m0.38s <--------------------------
sys 0m0.02s
kcsdev:/home/jmcnama>
kcsdev:/home/jmcnama> ./test 1
choice:1
Processing using short code... Done
kcsdev:/home/jmcnama> time ./test 0
choice:0
Processing using long code... Done

real 0m0.40s
user 0m0.38s <--------------------------
sys 0m0.01s
kcsdev:/home/jmcnama> time ./test 1
choice:1
Processing using short code... Done

real 0m6.79s
user 0m6.76s <--------------------------
sys 0m0.02s
kcsdev:/home/jmcnama>

The arrows point to the cpu usage in user mode, most of the real time the code used up doing the calculations...

jim mcnamara · 10-20-2003, 05:24 PM

This is the dataset in a header file "values.h"

Code:

/* values.h */
#define SIZE 1000
long values[SIZE] = {
   31025,    29531,      915,    28174,    29221,    11703,     6064,     2451,    11915,    14774,    24369, 
   19784,    28352,     8349,    20857,    27592,    27109,    28665,    30749,    19911,    21869, 
    6198,    16207,    14355,    22888,     6400,    24846,    21836,    32141,     5981,    22288, 
    8034,    23304,    14727,    32618,    25811,     7945,    25739,    24581,    26018,    10761, 
   14242,    13505,    17430,    22490,    24914,    13414,    17720,    15478,    10820,    14415, 
    7434,    24963,    20964,    13013,    17031,    20649,     6331,     8316,     1887,    30356, 
    5260,    24544,    28527,    10952,    10800,     7262,     1026,    26664,    18737,    14210, 
    7882,      580,    17705,    23859,    26780,    25446,    26841,    11936,     2030,     8026, 
    7944,    12265,    15122,    26369,    19745,    25742,    23088,    10388,    15244,    18072, 
   32005,    26809,    10184,     1161,    16478,     8264,    23629,    12804,    26450,    10970, 
   27171,    22332,    21570,     4629,    24642,     2846,     5522,    16826,     7336,     1086, 
     548,    28779,     4925,    19587,     8601,    18749,     9830,      913,    23623,     8706, 
   28011,    23545,    12024,    19027,     1161,    16163,    24168,    16224,    17111,    17399, 
   26237,    20599,    29145,    25678,     8516,       85,    25317,     7452,    25008,    12080, 
   32314,    25945,    32273,    22912,    10201,    10164,     1621,    30609,     5675,    10999, 
    8706,    18890,    30289,     5432,    20975,     7610,    31304,    30149,     4549,    22504, 
   11461,      461,     5433,    20055,     9930,    28622,     7431,    16347,      779,     7618, 
    8109,    29727,    11012,    28169,    16877,    20593,    22999,     1813,    23296,    27988, 
   28902,    25048,      154,    30916,    31285,    21229,    22178,    28999,    29821,    31368, 
    7853,     1464,    17679,    18207,    17216,     9683,    27503,    30421,    23234,     3967, 
   21164,    17323,    24131,    25823,    23680,     9829,     4079,     5911,      556,    23614, 
   19792,    12766,    10002,     6987,    18759,    21448,    30991,     8623,    27080,    24401, 
   31390,     2948,    17752,    12456,     4782,     7044,    31816,    25665,    15935,    25211, 
   27055,    31257,    16318,    29037,    26664,    25032,    26662,      647,     9809,    15176, 
   21971,    17606,    18174,    22663,    17700,    13929,    18753,    19374,    20184,    14871, 
   29723,     3631,    12326,    21200,    16894,     3217,    30873,    12950,     2058,     8955, 
   14770,     2007,    21764,    22146,     5180,    13729,    17430,    22322,    16237,    25220, 
   16201,     5854,    26049,     2630,    28099,      168,    29590,    32330,    18880,     7503, 
   13192,      189,     6737,    12347,    21642,    26246,    19671,     6474,    13769,    27626, 
   27198,     1880,     5185,    10242,     9210,    18321,    30235,    19167,    13507,    15734, 
   28621,     4727,     4368,    20400,     7920,     8790,     9045,    21911,    30432,    10757, 
    4092,    20866,    15126,     1593,    15651,      973,    17220,    18619,     6683,     8875, 
   25909,    21275,    25245,    17072,     8291,    28692,    22986,    15389,    26453,     6078, 
   14569,     6379,     8895,    19062,    19935,    22422,    19032,    11917,     1389,     3758, 
   12153,    23731,    23852,    15647,    21882,     1826,    31050,    21307,    29644,    26506, 
   23042,    16524,    32214,     8127,    27869,     4700,    19601,    31013,    30122,    28416, 
   17890,    11991,     2878,    31209,     7610,    11930,     9196,    27752,     3312,    31876, 
   28099,    28484,     6617,     9580,    28298,      254,    20141,    27664,    10108,    29919, 
   31129,     7433,    14532,    22214,    21155,    13679,    16567,    16307,     9026,    18508, 
   29395,    26386,    19385,    20161,     8827,    31944,    16951,    20218,    15728,     6143, 
   26544,     1491,    29199,    18098,    20089,    32583,    32077,     2551,    20134,    18845, 
   23666,    19215,     1059,    12113,    24216,     5423,     4757,     9155,    20963,     8204, 
   19182,    20130,    18557,    30505,     3794,    25110,    12632,    18912,     3501,    10160, 
   16547,    12338,    14225,    28690,    25609,    28750,      464,    20829,    16044,     4322, 
   22878,    24671,    26852,    17445,    24291,    20602,    28600,    30625,    18595,     9810, 
   20504,     5313,     1550,    26942,    27104,    15903,      294,    32620,     9869,     5514, 
    6549,     8402,    20413,    22232,    13706,     3288,    20841,    21362,     1111,    28358, 
   25569,     6808,    20172,     7407,    22923,    23160,    29009,     7835,     3162,    17907, 
   23493,     9397,    10000,     2858,    13082,    24889,    17972,     9930,    28845,    26972, 
   11475,     8220,     7014,     3704,     2294,    31180,    30356,    22974,      998,    25460, 
   17029,     5786,     6690,    30704,    27368,     6117,    30493,     5217,    16099,     9165, 
   20664,     5117,     3828,    12932,    32386,    31901,    19593,    27563,    18609,    26628, 
    1885,     3709,    10976,    13808,    25752,    12475,     1670,    21219,    27558,       91, 
     314,     8110,    17619,    29680,     2729,    17858,    17835,     5592,    18003,     1078, 
   26388,    22055,    21768,    16792,      295,     3927,    14886,    28275,    26835,    10668, 
   22671,     1188,    19248,     2408,    17260,    12125,    25252,    13235,    24229,    26614, 
   25016,    22089,     2844,     4983,    12216,     7649,    23212,    27878,    21260,     1889, 
    2020,    18513,     9561,     6083,    11651,    31386,    11607,     9925,    31155,    29189, 
   14961,    10323,    22790,    19331,     7710,     8373,    21809,    28860,     7938,    12152, 
    9099,     2782,      451,    23838,     8003,    22056,    17324,     6021,    11108,     8757, 
   25348,     2327,    14474,     2825,    20780,    14007,    27234,    14045,    27259,     4198, 
    6371,     9386,     4058,    24761,    10574,    22391,    15902,    18171,    31462,    27235, 
   16168,    10273,    25455,    22898,    20671,    17010,    30569,     2839,    23848,    20467, 
    6665,    26245,     8586,    25492,     4348,      694,    24069,    27931,     6107,    14904, 
   27532,     4052,    12140,    12218,    21382,    14325,     9374,     3930,    17705,     6867, 
    2883,     6316,     1169,     3527,    10379,    15754,    12194,    24542,     2372,    24990, 
   29859,     8772,    16340,     1712,     5783,     2926,     1522,    29104,    23387,    24841, 
   15911,     5251,    16257,     5285,     4360,    18574,     3054,    32545,     8752,     9731, 
   10549,    26325,     6400,     1006,    19634,    15490,    30998,    27902,    23399,    15098, 
    1678,     5396,     7830,    21903,    12795,     7053,     9762,     8509,    18467,     9808, 
   29862,     9367,    24958,     8598,    20818,    14962,    19821,    12412,    23434,    29523, 
   30011,     6730,    15421,     8601,    29396,    16513,     4357,    31850,    22343,    27046, 
   27907,     1374,    23805,    27857,     2936,     7406,      439,     2548,     4132,    29083, 
   17481,    31468,    29023,    13790,      536,     2378,    26616,    18642,    12372,    13534, 
     209,    15779,    27894,    14087,    11319,    28086,     9081,    28349,    26370,      406, 
   16728,      347,    22896,     7330,    13898,    15405,     1986,     6007,    15424,      702, 
   28820,    29982,     8986,    21982,    13565,    32501,     7213,    16245,     9835,    13151, 
   16758,    12043,    22075,    29483,    21659,     4883,      795,     6597,    29093,    15098, 
      32,    27679,    12671,    19956,    29094,     2653,    30766,    25217,    31723,    20547, 
   27342,      705,    16234,    20574,    18768,    10621,    16121,    22005,    10229,     1009, 
    2978,     6575,    17545,     1115,    21057,     5377,    29536,     4420,     9953,     8285, 
   24594,    23953,    10711,    18460,     7669,    13641,    25244,     1063,    17503,    19235, 
   27756,    15977,     4760,    21207,    20639,    21493,    22433,    29729,    10954,    31990, 
    6568,    25237,    29333,    18266,    14662,     9766,     1882,     4158,     3198,    24692, 
   22915,    10264,    11638,     6873,    19872,     3494,    30963,    26930,    13643,    27546, 
   30870,    28013,    31164,    17666,    13528,     2007,    21547,    31865,    10951,    16419, 
   12265,     8719,    24958,    13113,     4668,    13305,    23397,     4548,     9215,    15865, 
   24365,    31610,    14582,      908,    21642,    17194,    28914,     8405,    12463,    26503, 
   20137,    20044,    11915,    19638,    24659,    13094,    20165,      665,    22020,    29315, 
   23416,     9177,     8653,    24410,    27566,     6582,    32145,      804,     8862,    20622, 
   29351,    25419,     9894,    10542,    16180,    12625,     3079,    13020,    13638,    20929, 
   12130,    31264,    28593,    26070,    15350,    30807,    30890,    17388,    22935,    28661, 
   15908,     2730,    15981,    16797,    28654,    15085,     8306,     1506,     9097,     1139, 
   17065,    30683,    22986,    12620,     6687,    31849,    16948,    23553,    18083,    21063, 
   22547,    23681,    23364,    14038,    13657,     6095,    12943,     2982,    14136,     7789, 
   19077,    18628,    20611,    17799,    25694,    18374,     9669,     9952,    25600,    13207, 
   20254,    13181,    11070,    10499,    23521,    17683,    27857,    21505,    29679,    23090, 
   13079,     5572,    13010,    26926,     5773,    32640,     6297,    30160,    24590,    11773, 
   11382,    21953,     4809,    20957,    11544,    20402,     6659,    28844,    27337,      332, 
    5778,    10924,    10056,    14299,     2069,     4446,     5988,    10170,    19956, };

jim mcnamara · 10-20-2003, 05:25 PM

This is the algorithm I used:

Code:

/* isprime.c */
#ifndef BOOL
#define BOOL _
typedef unsigned long bool;
#define false 0
#define true 1
#endif
#include <math.h>
#include <stdlib.h>
#define PRIME_LIST 1000
/*MAXV is the square of the last member of the list */
#define MAXV 62710561
static long zero = 0;
static long found = 1;
static long primes[PRIME_LIST + 1]={
      2,      3,      5,      7,     11,     13,     17,     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,    311,    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,    569,    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,    827,    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,   1091,   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,   1321,   1327,   1361,   1367,   1373, 
   1381,   1399,   1409,   1423,   1427,   1429,   1433,   1439,   1447,   1451, 
   1453,   1459,   1471,   1481,   1483,   1487,   1489,   1493,   1499,   1511, 
   1523,   1531,   1543,   1549,   1553,   1559,   1567,   1571,   1579,   1583, 
   1597,   1601,   1607,   1609,   1613,   1619,   1621,   1627,   1637,   1657, 
   1663,   1667,   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,   1949,   1951,   1973,   1979,   1987, 
   1993,   1997,   1999,   2003,   2011,   2017,   2027,   2029,   2039,   2053, 
   2063,   2069,   2081,   2083,   2087,   2089,   2099,   2111,   2113,   2129, 
   2131,   2137,   2141,   2143,   2153,   2161,   2179,   2203,   2207,   2213, 
   2221,   2237,   2239,   2243,   2251,   2267,   2269,   2273,   2281,   2287, 
   2293,   2297,   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,   2579,   2591,   2593,   2609,   2617, 
   2621,   2633,   2647,   2657,   2659,   2663,   2671,   2677,   2683,   2687, 
   2689,   2693,   2699,   2707,   2711,   2713,   2719,   2729,   2731,   2741, 
   2749,   2753,   2767,   2777,   2789,   2791,   2797,   2801,   2803,   2819, 
   2833,   2837,   2843,   2851,   2857,   2861,   2879,   2887,   2897,   2903, 
   2909,   2917,   2927,   2939,   2953,   2957,   2963,   2969,   2971,   2999, 
   3001,   3011,   3019,   3023,   3037,   3041,   3049,   3061,   3067,   3079, 
   3083,   3089,   3109,   3119,   3121,   3137,   3163,   3167,   3169,   3181, 
   3187,   3191,   3203,   3209,   3217,   3221,   3229,   3251,   3253,   3257, 
   3259,   3271,   3299,   3301,   3307,   3313,   3319,   3323,   3329,   3331, 
   3343,   3347,   3359,   3361,   3371,   3373,   3389,   3391,   3407,   3413, 
   3433,   3449,   3457,   3461,   3463,   3467,   3469,   3491,   3499,   3511, 
   3517,   3527,   3529,   3533,   3539,   3541,   3547,   3557,   3559,   3571, 
   3581,   3583,   3593,   3607,   3613,   3617,   3623,   3631,   3637,   3643, 
   3659,   3671,   3673,   3677,   3691,   3697,   3701,   3709,   3719,   3727, 
   3733,   3739,   3761,   3767,   3769,   3779,   3793,   3797,   3803,   3821, 
   3823,   3833,   3847,   3851,   3853,   3863,   3877,   3881,   3889,   3907, 
   3911,   3917,   3919,   3923,   3929,   3931,   3943,   3947,   3967,   3989, 
   4001,   4003,   4007,   4013,   4019,   4021,   4027,   4049,   4051,   4057, 
   4073,   4079,   4091,   4093,   4099,   4111,   4127,   4129,   4133,   4139, 
   4153,   4157,   4159,   4177,   4201,   4211,   4217,   4219,   4229,   4231, 
   4241,   4243,   4253,   4259,   4261,   4271,   4273,   4283,   4289,   4297, 
   4327,   4337,   4339,   4349,   4357,   4363,   4373,   4391,   4397,   4409, 
   4421,   4423,   4441,   4447,   4451,   4457,   4463,   4481,   4483,   4493, 
   4507,   4513,   4517,   4519,   4523,   4547,   4549,   4561,   4567,   4583, 
   4591,   4597,   4603,   4621,   4637,   4639,   4643,   4649,   4651,   4657, 
   4663,   4673,   4679,   4691,   4703,   4721,   4723,   4729,   4733,   4751, 
   4759,   4783,   4787,   4789,   4793,   4799,   4801,   4813,   4817,   4831, 
   4861,   4871,   4877,   4889,   4903,   4909,   4919,   4931,   4933,   4937, 
   4943,   4951,   4957,   4967,   4969,   4973,   4987,   4993,   4999,   5003, 
   5009,   5011,   5021,   5023,   5039,   5051,   5059,   5077,   5081,   5087, 
   5099,   5101,   5107,   5113,   5119,   5147,   5153,   5167,   5171,   5179, 
   5189,   5197,   5209,   5227,   5231,   5233,   5237,   5261,   5273,   5279, 
   5281,   5297,   5303,   5309,   5323,   5333,   5347,   5351,   5381,   5387, 
   5393,   5399,   5407,   5413,   5417,   5419,   5431,   5437,   5441,   5443, 
   5449,   5471,   5477,   5479,   5483,   5501,   5503,   5507,   5519,   5521, 
   5527,   5531,   5557,   5563,   5569,   5573,   5581,   5591,   5623,   5639, 
   5641,   5647,   5651,   5653,   5657,   5659,   5669,   5683,   5689,   5693, 
   5701,   5711,   5717,   5737,   5741,   5743,   5749,   5779,   5783,   5791, 
   5801,   5807,   5813,   5821,   5827,   5839,   5843,   5849,   5851,   5857, 
   5861,   5867,   5869,   5879,   5881,   5897,   5903,   5923,   5927,   5939, 
   5953,   5981,   5987,   6007,   6011,   6029,   6037,   6043,   6047,   6053, 
   6067,   6073,   6079,   6089,   6091,   6101,   6113,   6121,   6131,   6133, 
   6143,   6151,   6163,   6173,   6197,   6199,   6203,   6211,   6217,   6221, 
   6229,   6247,   6257,   6263,   6269,   6271,   6277,   6287,   6299,   6301, 
   6311,   6317,   6323,   6329,   6337,   6343,   6353,   6359,   6361,   6367, 
   6373,   6379,   6389,   6397,   6421,   6427,   6449,   6451,   6469,   6473, 
   6481,   6491,   6521,   6529,   6547,   6551,   6553,   6563,   6569,   6571, 
   6577,   6581,   6599,   6607,   6619,   6637,   6653,   6659,   6661,   6673, 
   6679,   6689,   6691,   6701,   6703,   6709,   6719,   6733,   6737,   6761, 
   6763,   6779,   6781,   6791,   6793,   6803,   6823,   6827,   6829,   6833, 
   6841,   6857,   6863,   6869,   6871,   6883,   6899,   6907,   6911,   6917, 
   6947,   6949,   6959,   6961,   6967,   6971,   6977,   6983,   6991,   6997, 
   7001,   7013,   7019,   7027,   7039,   7043,   7057,   7069,   7079,   7103, 
   7109,   7121,   7127,   7129,   7151,   7159,   7177,   7187,   7193,   7207,
   7211,   7213,   7219,   7229,   7237,   7243,   7247,   7253,   7283,   7297, 
   7307,   7309,   7321,   7331,   7333,   7349,   7351,   7369,   7393,   7411, 
   7417,   7433,   7451,   7457,   7459,   7477,   7481,   7487,   7489,   7499, 
   7507,   7517,   7523,   7529,   7537,   7541,   7547,   7549,   7559,   7561, 
   7573,   7577,   7583,   7589,   7591,   7603,   7607,   7621,   7639,   7643, 
   7649,   7669,   7673,   7681,   7687,   7691,   7699,   7703,   7717,   7723, 
   7727,   7741,   7753,   7757,   7759,   7789,   7793,   7817,   7823,   7829, 
   7841,   7853,   7867,   7873,   7877,   7879,   7883,   7901,   7907,   7919, 0};
int comp(void *, void *);
long *findprime(register long);

bool isprime(long testval){
   	
   long *ptr;
   if(!testval%2) return false;
   if(testval <= primes[PRIME_LIST -1])   
          ptr=(long *) bsearch(&testval,primes,PRIME_LIST,sizeof(long),comp);
   else
          ptr=findprime(testval);
   return (*ptr!=0);
}
/* works for 32bit int types and 32 bit longs */
int comp(const void * a, const void * b){
   
   return (int) *(long*)a - *(long*)b; 
  
}
long *findprime(register long testval){
   register long *ptr;
   long midpoint;
   long result=0;
   for(ptr=primes;*ptr && !result;ptr++) if(!testval%*ptr)result=*ptr;
   if(!result){
       int i;
       midpoint=sqrt(testval);
       midpoint++;
       for(i=primes[PRIME_LIST-1];i<midpoint && !result; i+=2) if(!testval%i) result=i;       
       if(result) 
          ptr=&found;
       else
           ptr=&zero;   
   }
   return ptr;
}

jim mcnamara · 10-20-2003, 05:27 PM

And this is the test code driver, with your function added.
Not that I changed datatype to long, since the "long" algorithm was set to use a long datatype. On my system Long and int are the same thing, except that the compiler doesn't know that.

Code:

/* test.c */
#include <stdlib.h>
#include <stdio.h>
#include "values.h"
extern isprime(long);
int isprime1(long);



int main(int argc, char *argv[]){
    int i,j;
    int choice;

    choice=atoi(argv[1]);
    printf("choice:%d\n",choice);
    if (choice!=0) {/*plan B */
        printf("Processing using short code... ");
        for(i=0;i<SIZE;i++) j=isprime1(values[i]);
    }
    if(choice==0){
    	printf("Processing using long code... ");
        for(i=0;i<SIZE;i++) j=isprime(values[i]);
    }
    printf("Done\n");
    return 0;
}
/* your function renamed to isprime1 */
/* I made the dataypes long to match the algorithm I used.  
   on 32 bit systems, C usually makes long and int the same thing */
int
isprime1(long n)
{
long i = 1;	
if ((n>1)&&(n<4)) return 1;
if(!(n%2)) return 0;
while(((i+=2) <= sqrt(n))&&(n%i));
return (n%i);
}

Claus · 10-22-2003, 06:51 PM

Ok, I can see that is a lot faster.

But my question is... What happens to bigger numbers?

you need to create the table for biggest numbers, if needed... dont?

Primes will always be primes, that's right... but i dont know ... limitations on the size of the prime number? with the table, you'll have limitatios always... am i right?

I'm asking.. maybe you have more experiece than me. this conversation has become very interesant

Fascistchicken · 10-22-2003, 07:45 PM

a year or so ago three indian mathmaticians formulated a proof of primality
this is the only absoulte proof that i know of...
i wouldn't think it as fast as a table based system but certainly faster than
a brute force method and its claimed to be certain of correctness for any number...

http://www.cse.iitk.ac.in/news/primality.html

jim mcnamara · 10-22-2003, 08:20 PM

I threw that stuff together - it has a bug or two.

Our production code uses a table that handles all positve long values - the first 4797 primes - up to 2.7 billion.

It can find 100000 primes in 8 seconds on our HP multiuser box.
We use it in production because we evaluate primality of numbers about 300,000 times an hour.

bsearch is okay for small primes, but the best application is to use the pointer stomp thru the prime list.

The reason is that 98%+ of all integers are factored by the first 201 prime numbers. Therefore the search returns on average after about 100 iterations for really large numbers. Using a midpoint break based on sqrt speeds up exit on medium sized primes.